Is it possible not to use nested loops in a permutation problem?

Question

I am writing a code which prints all the permutations of [a,b,c,d].I don't want to use recursive function and instead I have used 4 for loops, but the disadvantage of my code is that the loops have to be the same amount as the elements of the list. My question is that wether it is possible to write a code which is independent from the number of the elements.

alphabet=["a","b","c","d"]
for first in alphabet:
    for second in alphabet:
        if second != first:
            for third in alphabet:
                if third!=second and third!=first :
                    for fourth in alphabet:
                        if fourth!=first and fourth!=second and fourth != third:         
                            print(first,second,third,fourth)

Check out [itertools](https://docs.python.org/3/library/itertools.html) — , Dec 29 '18 at 13:42
Hmm perhaps you should edit your question's title..is it about nested loops or about independency with the length of the list..? — , Dec 29 '18 at 14:55
This will fail on something like alphabet = ['a', 'a'] (or at least give different results from how everyone else does permutations, including itertools.permutations) To use this approach, you would need indexes, which will be distinct. — Kenny Ostrom, Dec 29 '18 at 16:23

score 3 · Answer 1 · answered Dec 29 '18 at 13:45

The code is hard to understand, but yes it is possible, you can look at it inside the Python documentation:

https://docs.python.org/2/library/itertools.html#itertools.permutations

Relevant sections extracted from the link for reader confort (I invoke fair use):

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

The code for permutations() can be also expressed as a subsequence of product(), filtered to exclude entries with repeated elements (those from the same position in the input pool):

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

If you are going to copy another answer verbatim, you might want reference it. Or just vote close as duplicate. — user2390182, Dec 29 '18 at 13:55
@schwobaseggl I did not copy another answer, I copied the Python documentation. Probably the other answer is the same by chance. Feel free to close as duplicate if the content is the same — Caridorc, Dec 29 '18 at 14:44

user2390182 · Answer 2 · 2018-12-29T14:01:59.200

Here is a non-recursive attempt that relies on there being no duplicates in the initial pool:

from collections import deque

def perms(pool):
    agenda = deque([([], pool)])
    while agenda:
        perm, left = agenda.popleft()
        if not left:
            yield perm
            # Or, to mimic the original 
            # print(*perm)
        else:
            for x in left:
                agenda.append((perm+[x], [y for y in left if y != x]))

>>> list(perms('abc')))
[['a', 'b', 'c'],
 ['a', 'c', 'b'],
 ['b', 'a', 'c'],
 ['b', 'c', 'a'],
 ['c', 'a', 'b'],
 ['c', 'b', 'a']]

score 0 · Answer 3 · 2018-12-29T14:52:17.103

This is one basic way (quite easy to come up with).

Start easy first. To start, let alpha = ["a", "b", "c", "d"]. First find all permutations that start with "a":

    start_a = [["a"]]

    two_start_a = [ start_a[0] + [i]  for i in alpha ]

    to_three_start_a = [ [ j + [i] for i in alpha ] for j in two_start_a ]
    three_start_a = []
    for i in to_three_start_a:
        #cleaned is to exclude list with multiple values
        cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 
        three_start_element += cleaned

    to_four_start_a = [ [ j + [i] for i in alpha ] for j in three_start_a ]
    four_start_a = []
    for i in to_four_start_a:
        #cleaned is to exclude list with multiple values
        cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 
        four_start_element += cleaned

Now our four_start_a consists all permutations that start with "a". The automated version is

    start_a = [[alpha[0]]]

    two_start_a = [ start_a[0] + [i]  for i in alpha ]
    k_start_element = two_start_element
    for k in range(3, len(alpha)+1): 
        to_k_start_a = [ [ j + [i] for i in alpha ] for j in k_start_element ]
        k_start_a = []
        for i in to_k_start_a:
            #cleaned is to exclude list with multiple values
            cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 
            k_start_element += cleaned

Then the final k_start_a is all the permutations that start with the first element of alpha.

Solution

So, for all letters, we can automate as below

all_permutations = []
for element in alpha:

    start_element = [[element]]

    two_start_element = [ start_element[0] + [i]  for i in alpha ]

    k_start_element = two_start_element
    for k in range(3, len(alpha)+1): 
        to_k_start_element = [ [ j + [i] for i in alpha ] for j in k_start_element ]
        k_start_element = []
        for i in to_k_start_element:
            #to exclude list with multiple values
            cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 
            k_start_element += cleaned


    all_permutations.extend( k_start_element )

Is it possible not to use nested loops in a permutation problem?

3 Answers3