The Combination Function and Iterator using Depth First Search A
- 时间:2020-09-13 14:33:25
- 分类:网络文摘
- 阅读:102 次
The combination algorithm returns the sequence for a list or string without considering the order. For example, the Combination of string “abc” with two characters would be “ab”, “ac” and “bc”.
The number of combination for n-size elements using m elements can be computed as:

combination-formula
For example, Picking 2 elements out of 3 has three solutions: 3!/(2!*(3-2)!) = 3
Solving Combination via DFS Algorithm
We can use the DFS (Depth First Search) algorithm to start picking elements until we have picked the desired number of items. For each iteration, we can choose to pick or not pick the current element. The DFS can be easily implemented via Recursion.
In the following C++ function, we define a recursive combination function that will push all the results into a vector (pass by reference). We pass a position variable and we will only pick in current iteration the elements to the right of this position.
1 2 3 4 5 6 7 8 9 10 11 12 | void combination(string alphabeta, int toPick, vector<string> &result, string s = "", int pos = 0) { if (s.size() == toPick) { // found a solution result.push_back(s); } if (pos == alphabeta.size()) { // reach the end of items return; } for (int i = pos; i < alphabeta.size(); ++ i) { // picking this element, then start picking elements to the right combination(alphabeta, toPick, result, s + alphabeta[i], i + 1); } } |
void combination(string alphabeta, int toPick, vector<string> &result, string s = "", int pos = 0) { if (s.size() == toPick) { // found a solution result.push_back(s); } if (pos == alphabeta.size()) { // reach the end of items return; } for (int i = pos; i < alphabeta.size(); ++ i) { // picking this element, then start picking elements to the right combination(alphabeta, toPick, result, s + alphabeta[i], i + 1); } }
However, the DFS may not be optimal, the complexity is N elements first iteration, N-1 second iteration etc thus N*(N-1)*(N-2)*…(N-M), roughly to O(N^M).
Python Combination Function
We can implement in Python the following combination function that works for both List and String:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def combinations(data, length): r = [] def dfs(cur, pos): if len(cur) == length: r.append(cur) if pos == len(data): return if type(data) is list: for i in range(pos, len(data)): dfs(cur + [data[i]], i + 1) else: for i in range(pos, len(data)): dfs(cur + data[i], i + 1) if type(data) is list: dfs([], 0) else: dfs("", 0) return r |
def combinations(data, length): r = [] def dfs(cur, pos): if len(cur) == length: r.append(cur) if pos == len(data): return if type(data) is list: for i in range(pos, len(data)): dfs(cur + [data[i]], i + 1) else: for i in range(pos, len(data)): dfs(cur + data[i], i + 1) if type(data) is list: dfs([], 0) else: dfs("", 0) return r
A local recursive DFS function is defined, and we use type() to deal with the list (array) or the string. Example usage:
1 2 3 4 5 6 | print(combinations([1, 2, 3, 4], 2)) >>> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] print(combinations(['a', 'b', 'c', 'd'], 2)) >>> [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']] print(combinations('abcd', 2)) >>> ['ab', 'ac', 'ad', 'bc', 'bd', 'cd'] |
print(combinations([1, 2, 3, 4], 2)) >>> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] print(combinations(['a', 'b', 'c', 'd'], 2)) >>> [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']] print(combinations('abcd', 2)) >>> ['ab', 'ac', 'ad', 'bc', 'bd', 'cd']
Python Combination Iterator
If we are not using all the combination results at once, we can modify the above Python algorithm to return a iterator – which avoids sucking up memory at once. Each result is yield-ed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def combinations(data, length): def dfs(cur, pos): if len(cur) == length: yield cur if pos == len(data): return if type(data) is list: for i in range(pos, len(data)): for j in dfs(cur + [data[i]], i + 1): yield j else: for i in range(pos, len(data)): for j in dfs(cur + data[i], i + 1): yield j if type(data) is list: return dfs([], 0) else: return dfs("", 0) |
def combinations(data, length): def dfs(cur, pos): if len(cur) == length: yield cur if pos == len(data): return if type(data) is list: for i in range(pos, len(data)): for j in dfs(cur + [data[i]], i + 1): yield j else: for i in range(pos, len(data)): for j in dfs(cur + data[i], i + 1): yield j if type(data) is list: return dfs([], 0) else: return dfs("", 0)
As the combinations function now returns an iterator, we can use it like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | for i in combinations_iterator([1, 2, 3, 4], 2): print(i) # [1, 2] # [1, 3] # [1, 4] # [2, 3] # [2, 4] # [3, 4] for i in combinations_iterator(['a', 'b', 'c', 'd'], 2): print(i) # ['a', 'b'] # ['a', 'c'] # ['a', 'd'] # ['b', 'c'] # ['b', 'd'] # ['c', 'd'] for i in combinations_iterator('abcd', 2): print(i) # ab # ac # ad # bc # bd # cd |
for i in combinations_iterator([1, 2, 3, 4], 2): print(i) # [1, 2] # [1, 3] # [1, 4] # [2, 3] # [2, 4] # [3, 4] for i in combinations_iterator(['a', 'b', 'c', 'd'], 2): print(i) # ['a', 'b'] # ['a', 'c'] # ['a', 'd'] # ['b', 'c'] # ['b', 'd'] # ['c', 'd'] for i in combinations_iterator('abcd', 2): print(i) # ab # ac # ad # bc # bd # cd

python
Another interesting read to implement the combination using bitmasking algorithm: Using Bitmasking Algorithm to Compute the Combinations of an Array
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:吃中秋月饼有三个较好的搭配食物 经常食用新鲜西红柿的10大益处 在感冒发烧时应该如何安排饮食 十种常见食物搭配吃得营养又健康 日常食物怎样搭配吃出加倍营养? 秋冬季这样吃南瓜可防治便秘胃痛 三种豆子一起吃营养效果最好 红糖对女人健康有三大养生功效 南瓜的养生功效:温润脾胃护心助眠 可以用豆浆替代牛奶来补钙吗?
- 评论列表
-
- 添加评论