Permutations without itertools for two values (using recursion!)

Question

Stackoverflow, I am once again asking for your help.

I'm aware there are other threads about this but I'll explain what makes my assignment different.

Basically my function would get a list of 0s and 1s, and return all the possible orders for the string. For example for "0111" we will get "0111", "1011", "1101", "1110".

Here's my code:

def permutations(string):
    if len(string) == 1:
        return [string]

    lst = []

    for j in range(len(string)):
        remaining_elements = ''.join([string[i] for i in range(len(string)) if i != j])
        mini_perm = permutations(remaining_elements)

        for perm in mini_perm:
            new_str = string[j] + perm
            if new_str not in lst:
                lst.append(new_str)

    return lst

The problem is when I run a string like "000000000011" it takes a very long time to process. There is supposed to be a more efficient way to do it because it's just two numbers. So I shouldn't be using the indexes?

Please help me if you can figure out a more efficient say to do this.

(I am allowed to use loops just have to use recursion as well!)

You could always check the itertools source code for how it is implemented and do something similar if you do not wish to use the module. docs.python.org/3/library/itertools.html#itertools.permutations — PacketLoss
– PacketLoss, Commented May 11, 2021 at 14:18
@PacketLoss The itertools permutations function is even slower than the customized version I wrote, because it would repeat similar objects. This is supposed to be possible in basic Python - recursion, for, loops, no OOP. — kanyeeast
– kanyeeast, Commented May 11, 2021 at 14:25
@PacketLoss it should return "000000000011", "000000000101", "000000001001" etc. — kanyeeast
– kanyeeast, Commented May 11, 2021 at 14:35

flooo · Accepted Answer · 2021-05-11 15:03:31Z

1

Here is an example for creating permutations with recursion that is more efficient:

def permute(string):
    string = list(string)
    n = len(string)

    # Base conditions
    # If length is 0 or 1, there is only 1 permutation
    if n in [0, 1]:
        return [string]

    # If length is 2, then there are only two permutations
    # Example: [1,2] and [2,1]
    if n == 2:
        return [string, string[::-1]]

    res = []
    # For every number in array, choose 1 number and permute the remaining
    # by calling permute recursively
    for i in range(n):
        permutations = permute(string[:i] + string[i+1:])
        for p in permutations:
            res.append([''.join(str(n) for n in [string[i]] + p)])

    return res

This should also work for permute('000000000011') - hope it helps!

answered May 11, 2021 at 15:03

flooo

266 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ajax1234 · Accepted Answer · 2021-05-11 16:16:07Z

You can also use collections.Counter with a recursive generator function:

from collections import Counter
def permute(d):
   counts = Counter(d)
   def get_permuations(c, s = []):
     if len(s) == sum(counts.values()):
        yield ''.join(s)
     else:
        for a, b in c.items():
           for i in range(1, b+1):
              yield from get_permuations({**c, a:b - i}, s+([a]*i))
   return list(set(get_permuations(counts)))

print(permute("0111"))
print(permute("000000000011"))

Output:

['0111', '1110', '1101', '1011']
['010000100000', '100000000001', '010000001000', '000000100001', '011000000000', '100000000010', '001001000000', '000000011000', '100000001000', '100000100000', '100001000000', '001000100000', '100010000000', '000000001100', '000100000100', '010010000000', '000000000011', '000000100010', '101000000000', '110000000000', '100000010000', '000100001000', '000001001000', '000000000101', '000000100100', '010000000001', '001000000100', '001000000010', '000110000000', '000011000000', '000001100000', '000000110000', '001000000001', '000010001000', '000100100000', '000001000001', '000010000001', '001100000000', '000100000001', '001000001000', '010000000100', '010000010000', '000000010001', '001000010000', '010001000000', '100000000100', '100100000000', '000000001001', '010100000000', '000010100000', '010000000010', '000000001010', '000010000100', '001010000000', '000000010010', '000001000010', '000100000010', '000101000000', '000000010100', '000100010000', '000000000110', '000001000100', '000010010000', '000000101000', '000001010000', '000010000010']

kanyeeast · Accepted Answer · 2021-05-12 20:36:53Z

0

posting an answer someone gave me. Thanks for your responses!:

def permutations(zeroes, ones, lst, perm):
    if zeroes == 0 and ones == 0:
        lst.append(perm)
        return
    elif zeroes < 0 or ones < 0:
        return
    
    permutations(zeroes - 1, ones, lst, perm + '0')
    permutations(zeroes, ones - 1, lst, perm + '1')

answered May 12, 2021 at 20:36

kanyeeast

454 bronze badges

Collectives™ on Stack Overflow

Permutations without itertools for two values (using recursion!)

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related