-1

i've tried this approach and it went wrong. so, any ideas how to fix this snippet?

def swap(seq, i , j):
    temp = 0
    temp = seq[i]
    seq[i] = seq[j]
    seq[j] = temp

def all_possible_strings(seq):
    list_of_results = []
    for i in range(len(seq)):
        for j in range(len(seq)):
            copy_of_seq = seq[:]

            swap(copy_of_seq, i ,j)

            list_of_results.append("".join(copy_of_seq))

    return list_of_results

here is the output: ['abc', 'bac', 'cba', 'bac', 'abc', 'acb', 'cba', 'acb', 'abc']

zibra22
  • 1
  • 1
  • What should the output be instead? I suggest you read [this article](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) for tips on debugging your code. – Code-Apprentice Nov 06 '19 at 16:46
  • this should be the output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] – zibra22 Nov 06 '19 at 16:49

2 Answers2

3

Your algorithm cannot possibly account for all the permutations.

Notice that the pair (i,j) can be any index pair. However, for each of your permutations in your code, you start with the original string and apply one swap. This cannot possibly get you all the permutations.

Pretend you start with ABCD. If you wanted the reverse permutation DCBA, you would not be able to do this in a single swap. A single swap will at most change the positions of 2 characters, but all 4 characters need to be in a different place.

Note that the number of possible (i,j) pairs for a list of size n is n*n = n^2, which is not the same as the expected number of permutations n!. In almost all cases, n! > n^2, which means there definitely will be missing permutations.

In addition, you have pairs like (1,1) which results in a swap that does nothing (which is fine, except now (2,2), (3,3), etc. give duplicate permutations) [thanks Code-Apprentice for pointing that out]. You also have both (1,2) which will result in ACBD, as well as (2,1), which also results in ACBD. This is why you have duplicate permutations in your final permutation list.

P.S. In Python, you can swap two elements by simply doing a,b = b,a.

Heap's Algorithm

The correct implementation of this is to use something like Heap's algorithm, which is a proper, more sophisticated switching of elements to obtain all the permutations.

Instead of making a new copy of the list each time, you keep doing swaps on the same list and it will cycle through all of the permutations, provided you do them in the correct order specified by the algorithm.

I won't bother detailing the algorithm here since the resources do a great job explaining it. If you really need an explicit Python implementation example, that's also easy to find.

CosmoVibe
  • 223
  • 1
  • 7
2

You can use itertools.permutations:

import itertools

seq = 'abc'
list_of_results = [''.join(p) for p in itertools.permutations(seq)]
print(list_of_results)

Output:

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Sumner Evans
  • 8,951
  • 5
  • 30
  • 47
  • i want to practice the ordinary solution just to grasp the idea of string permutation – zibra22 Nov 06 '19 at 16:50
  • @MohamedAbdElsattar, This thread also include the link on how permutation is been implemented. So you should be fine if you are behind the math. – S.N Nov 06 '19 at 16:58