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

user_10846260 0
Viewed 756

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)
nested-loops python
3 Answers

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)
user_31054850

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']]
user_23901820

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 )
Admin1
Related