The Combination Function and Iterator using Depth First Search A

  • 时间：2020-09-13 14:33:25
  • 分类：网络文摘
  • 阅读：158 次

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 The Combination Function and Iterator using Depth First Search Algorithm algorithms c / c++ DFS python

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 The Combination Function and Iterator using Depth First Search Algorithm algorithms c / c++ DFS python

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个注意 饮食搭配有原则　 秋冬进补忌选狗肉 不可不知的进补攻略　 养生又保健：柚子皮的神奇做法　 选择有机食品真的更有营养吗？　
评论列表
添加评论