All permutations of an array in python-CodePudding

I have an array. I want to generate all permutations from that array, including single element, repeated element, change the order, etc. For example, say I have this array:

arr = ['A', 'B', 'C']

And if I use the itertools module by doing this:

from itertools import permutations
perms = [''.join(p) for p in permutations(['A','B','C'])]
print(perms)

Or using loop like this:

def permutations(head, tail=''):
if len(head) == 0:
    print(tail)
else:
    for i in range(len(head)):
        permutations(head[:i]   head[i 1:], tail   head[i])
        
arr= ['A', 'B', 'C']
permutations(arr)

I only get:

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

But what I want is:

['A', 'B', 'C', 
 'AA', 'AB', 'AC', 'BB', 'BA', 'BC', 'CA', 'CB', 'CC', 
 'AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ACA', 'ACC', 'BBB', 'BAA', 'BAB', 'BAC', 'CCC', 'CAA', 'CCA'.]

The result is all permutations from the array given. Since the array is 3 element and all the element can be repetitive, so it generates 3^3 (27) ways. I know there must be a way to do this but I can't quite get the logic right.

CodePudding user response：

A generator that would generate all sequences as you describe (which has infinite length if you would try to exhaust it):

from itertools import product


def sequence(xs):
    n = 1
    while True:
        yield from (product(xs, repeat=n))
        n  = 1


# example use: print first 100 elements from the sequence
s = sequence('ABC')
for _ in range(100):
    print(next(s))

Output:

('A',)
('B',)
('C',)
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'A')
('B', 'B')
('B', 'C')
('C', 'A')
('C', 'B')
('C', 'C')
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'A', 'C')
('A', 'B', 'A')
...

Of course, if you don't want tuples, but strings, just replace the next(s) with ''.join(next(s)), i.e.:

    print(''.join(next(s)))

If you don't want the sequences to exceed the length of the original collection:

from itertools import product


def sequence(xs):
    n = 1
    while n <= len(xs):
        yield from (product(xs, repeat=n))
        n  = 1


for element in sequence('ABC'):
    print(''.join(element))

Of course, in that limited case, this will do as well:

from itertools import product

xs = 'ABC'
for s in (''.join(x) for n in range(len(xs)) for x in product(xs, repeat=n 1)):
    print(s)

Edit: In the comments, OP asked for an explanation of the yield from (product(xs, repeat=n)) part.

product() is a function in itertools that generates the cartesian product of iterables, which is a fancy way to say that you get all possible combinations of elements from the first iterable, with elements from the second etc.

Play around with it a bit to get a better feel for it, but for example:

list(product([1, 2], [3, 4])) == [(1, 3), (1, 4), (2, 3), (2, 4)]

If you take the product of an iterable with itself, the same happens, for example:

list(product('AB', 'AB')) == [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

Note that I keep calling product() with list() around it here, that's because product() returns a generator and passing the generator to list() exhausts the generator into a list, for printing.

The final step with product() is that you can also give it an optional repeat argument, which tells product() to do the same thing, but just repeat the iterable a certain number of times. For example:

list(product('AB', repeat=2)) == [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

So, you can see how calling product(xs, repeat=n) will generate all the sequences you're after, if you start at n=1 and keep exhausting it for ever greater n.

Finally, yield from is a way to yield results from another generator one at a time in your own generator. For example, yield from some_gen is the same as:

for x in some_gen:
    yield x

So, yield from (product(xs, repeat=n)) is the same as:

for p in (product(xs, repeat=n)):
    yield p