Given a string, return all possible combinations

Example: abc
returns a,b,c,ab,ac,bc,ca,cb,abc,acb,bac,bca,cab,cba

Reply content:

Example: abc
returns a,b,c,ab,ac,bc,ca,cb,abc,acb,bac,bca,cab,cba

I think this question is quite interesting. As a Python fanatic, I cannot agree with @garry_qian’s answer. Since Python provides such a useful standard library, it would be a pity not to use it. From this standpoint, a concise, short (well, no...), but basically logically the same approach is as follows:

<code>>>> s = 'abc'
>>> results = sorted([''.join(c) for l in range(len(s)) for c in permutations(s, l+1)])

['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

There is nothing special about this writing method, it is just a forlist comprehension using two s.
At the same time, it returns a list of strings, which is closer to the original question.

---

But this sparked some curiosity in me, and I wanted to write it myself. At the same time, in other languages ​​that do not have these permutation and combination tools, it may be easier to use the same logic to complete it.

The first thing I completed was the function about combination, which substitutes a string and returns all character combinations of all lengths, but does not arrange them:

<code>def get_combinations(string):
    combs = []
    for i in range(1, 2**len(string)):
        pat = "{0:b}".format(i).zfill(len(string))
        combs.append(''.join(c for c, b in zip(string, pat) if int(b)))
    return combs</code>

Test:

<code>>>>　print get_combinations('abc')
['c', 'b', 'bc', 'a', 'ac', 'ab', 'abc']</code>

As expected, we got:

1. 'c', 'b', 'a'

of length 1

2. 'bc', 'ac', 'ab'

of length 2

3. length 3 'abc'

As expected, all combinations of various lengths are available.

This way of writing is definitely not the best, but I think the idea is interesting. The idea is to consider all combinations of 'abc'. That means considering whether to take a, whether to take b and whether to take c, so there are a total of 2*2*2 = 8 (2**len(string)) combinations. , then doesn’t it correspond to:

<code>000 -> 都不取
001 -> 只取 c
010 -> 只取 b
011 -> 取 b c
100 -> 只取 a
101 -> 取 a c
110 -> 取 a b
111 -> 都取</code>

So in get_combinations, I used a little trick to generate binary codes from 1 to 7, and then decided which characters should be used in each combination based on 0 and 1.

---

This has not yet completed the task. We still have to obtain the standard answer:

All permutations situations for each

combination

This produces get_permutations the function:

<code>def get_permutations(clst):
    if len(clst)==1:
        return [clst[0]]
    results = []
    for idx, c in enumerate(clst):
        results += [c+substr for substr in get_permutations(clst[:idx] + clst[idx+1:])]
    return results</code>

Test:

<code>>>>　print get_permutations('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

The logic is very simple, use recursive method to find all the permutations of 固定長度字元組合.

---

With the above two functions, we can find the answer:

<code>>>> [perm for comb in get_combinations('abc') for perm in get_permutations(list(comb))]
['c', 'b', 'bc', 'cb', 'a', 'ac', 'ca', 'ab', 'ba', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

---

Conclusion:

1. Don’t reinvent tires, it will not only tire you out, but also make you look stupid

2. Life is short, I use Python

<code>import itertools

chrs = 'abc'

for i in range(len(chrs)):
    for combination in itertools.permutations(chrs, i + 1):
        print combination</code>

Since the php and python tags are marked at the same time, let’s write them in both ways. The logic is the same.

phpCode

<code class="php">function addChar($strs, $chars) {
    $result = [];
    foreach ($strs as $str) {
        foreach ($chars as $char) {
            $result[] = $str . $char;
        }
    }
    return $result;
}

$chars  = ['a', 'b', 'c'];

$group = [];
$count = count($chars);
for ($i = 1; $i <= $count; $i++) { 
    if ($i == 1) {
        $group[$i] = addChar([''], $chars);
    } else {
        $group[$i] = addChar($group[$i - 1], $chars);
    }
}

// 合并数组
$result = call_user_func_array('array_merge', $group);

var_dump($group);</code>

pythonCode

<code class="python"># encoding:utf-8

def addChar(strs, chars):
    result = []
    for str in strs:
        for char in chars:
            result.append(str + char)
    return result



chars = ['a', 'b', 'c']

group = {}
count = len(chars)

for i in xrange(1, count + 1):
    if i == 1:
        group[i] = addChar([''], chars)
    else:
        group[i] = addChar(group[i - 1], chars)

# 合并数组
result = []
for i in group:
    result += group[i]

print result
</code>

<code>result = [] 

def function(arg, string):
    global result

    if len(arg) >= len(string):
        return None 

    for alphabet in string:
        if alphabet in arg:
            continue
        function(arg+alphabet, string)
        result.append(arg+alphabet)

string = 'abc'

for alphabet in string:
    result.append(alphabet)
    function(alphabet, string)

print list(set(result))</code>

python2.7, the same as @garry_qian, I only found out after writing it. I am too lazy to look at other python solutions

<code class="python"># coding: utf-8
import itertools as t

li = ['a', 'b', 'c']
tmp = []
for n in range(1, len(li) + 1):
    x = t.permutations(li, n)
    for i in x:
        tmp.append(''.join(i))
print tmp</code>

P(2,3)
P(3,3)
12 possibilities

Assume the length of the string is 2, then all the combinations are: 2! 2! / 1! = 4
Assume the length of the string is 3, then all the combinations are: 3! 3! / 1! 3! / 2! = 15
Assume the length of the string is 4, then all the combinations are: 4! 4! / 1! 4! / 2! 4! / 3! = 64
This formula can be carried out Promotion
n! n! / 1! n! / 2! ... n! / (n-1)!

The code will not be posted