Obtaining recursively permutations of a single list-CodePudding

I am working in Python and I would like to obtain some kind of 'permutations' of a single list. I will make my best to explain the problem, but let me know if there is any doubt.

Imagine we have a list of strings a = ['?','A','A','A'], i.e. there are three 'A' elements: n=3. I would like to create a method to obtain all the permutations of the 'A's (and the rest of the elements being '?'), decrementally, in the sense that in each 'permutation layer', the number of 'A's is decremented by one: n=n-1.

With examples, this is understood much better:

E.g., for a we would obtain a0 = ['?','A','A','?'], a1 = ['?','A','?','A'] and and a2 = ['?','?','A','A'] in the first 'permutation layer' (n=3-1). In the same way, in the second 'permutation layer' (n=3-1-1); for a0 we would have a00 = ['?','A','?','?'] and a01 = ['?','?','A','?'], for a1 we would have a10 = ['?','A','?','?'] and a11 = ['?','?','?','A'] and for a2 we would have a20 = ['?','?','A','?'] and a21 = ['?','?','?','A']. I know some of them can be redundant, for instance, a00 and a10; there is no problem with that.

Note that there are no more permutation layers once n=1 is reached, since every result would be aN = ['?','?','?','?'].

A clarification: the layer DOES matter, since I want to test whether a list holds a property (not important to mention) to get deeper on the layer. I will explain better: if a0 holds that property, then we explore a00 and a01, else we will not. This way, we potentially do NOT explore all the permutations. Thus, I only need the method that, given a list, obtains the permutations of the immediately NEXT layer, not the rest of them. In case n=1, returns whatever, say foo.

I do not know how to find about this or similar problems (indeed, is it correct to talk about permutations?). The closest post here seems to be Recursive list of permutations, where terms like 'cartesian product' and 'combinations with repetition' are mentioned. But the problem is not the same.

I do not care which method is used to reach the solution, I am not looking for efficiency; however, I have the feeling that this can be done in an elegant way doing recursion over n.

Can anyone solve my problem? I would appreciate the code is given in Python or a similar language.

EDIT 1

Using itertools.permutations() does not produce the desired results:

import itertools
a = ['?', 'A', 'A', 'A']

b = itertools.permutations(a)
for j in list(b): 
    print(j)

This prints:

('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')

Note that there is no single one of the expected results in there, since the number of As has not been decremented.

CodePudding user response：

It sounds like you want a way to list all of the ways to replace some subset of the As with ?s, which means it is the same as finding all of the ways to choose a subset of the As (which itertools has code for).

CodePudding user response：

Those aren't really permutations. They are the product of 4 ['A','?'] lists.

You could get them without recursion using itertool's product function:

from itertools import product

for p in product(*['A?']*4): print(p)
('A', 'A', 'A', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', '?', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', '?')
('A', '?', '?', 'A')
('A', '?', '?', '?')
('?', 'A', 'A', 'A')
('?', 'A', 'A', '?')
('?', 'A', '?', 'A')
('?', 'A', '?', '?')
('?', '?', 'A', 'A')
('?', '?', 'A', '?')
('?', '?', '?', 'A')
('?', '?', '?', '?')

For a recursive version, you can pass down each value (A or ? down the recursion with n-1 as the count:

def prod(values,n,result=[]):
    for v in values:
        if n == 1: yield [*result,v]
        else: yield from prod(values,n-1,[*result,v])