GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python-1/backtracking/all_combinations.py at master · https-github-com-nzysoft/Python-1 Expand file tree/ Copy pathall_combinations.pyMore file actions 46 lines (36 loc) · 1.19 KB / Copy pathall_combinations.pyFile metadata and controls46 lines (36 loc) · 1.19 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 """ In this problem, we want to determine all possible combinations of k numbers out of 1 ... n. We use backtracking to solve this problem. Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!))) """ from __future__ import annotations def generate_all_combinations(n: int, k: int) -> list[list[int]]: """ >>> generate_all_combinations(n=4, k=2) [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] """ result: list[list[int]] = [] create_all_state(1, n, k, [], result) return result def create_all_state( increment: int, total_number: int, level: int, current_list: list[int], total_list: list[list[int]], ) -> None: if level == 0: total_list.append(current_list[:]) return for i in range(increment, total_number - level + 2): current_list.append(i) create_all_state(i + 1, total_number, level - 1, current_list, total_list) current_list.pop() def print_all_state(total_list: list[list[int]]) -> None: for i in total_list: print(*i) if __name__ == "__main__": n = 4 k = 2 total_list = generate_all_combinations(n, k) print_all_state(total_list) |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |