CODEWITHSUNDEEP
pythonalgorithmpermutation
Manie
Manie

Reputation: 2028

Python implementation for permutation given specific conditions

How can I generate permutations given the following conditions?

  1. There are two integers, for ex. 1 and 4.
  2. The two integers given will be part of the permutation where each integer will appear at most N times and the size of each permutation is K.

So let's say for N = 3 and K = 5, so the correct result should be:

{1, 1, 1, 4, 4} , {1, 1, 4, 1, 4} , {4, 4, 4, 1, 1} , etc..

The following are example of invalid or incorrect results:

{1, 1, 1, 1, 4} -> 1 appear 4 times (1 should appear not greater than 3 times)

{1, 4, 4, 4, 1, 1} -> the size of the list is 6 (the size should be exactly 5)

Also, each permutation should be unique, meaning no duplicates.

I hope I can get the best solution or algorithm for this problem.

Thanks in advance. :)

Upvotes: 3

Views: 1215

Answers (4)

Janne Karila
Janne Karila

Reputation: 25197

Starting from here (as in Abhijit's answer)...

>>> K=5
>>> N=3
>>> [['1']*n+['4']*(K-n) for n in xrange(K-N,N+1)]
[['1', '1', '4', '4', '4'], ['1', '1', '1', '4', '4']]

...you could then Generate permutations of list with repeated elements for each list. Also, handle the case if N < K-N, perhaps by setting N=max(N,K-N)

Upvotes: 2

Abhijit
Abhijit

Reputation: 63727

See if this works for you

>>> K=5
>>> N=3
>>> src=[['1']*n+['4']*(K-n) for n in xrange(K-N,N+1)]
>>> set(x for s in src for x in itertools.permutations(s))
set([('1', '4', '1', '4', '1'), ('4', '1', '4', '1', '1'), ('1', '1', '4', '4', '4'), ('1', '4', '4', '1', '1'), ('1', '4', '4', '4', '1'), ('4', '4', '4', '1', '1'), ('4', '1', '1', '4', '1'), ('4', '4', '1', '4', '1'), ('1', '4', '1', '1', '4'), ('4', '1', '4', '4', '1'), ('1', '1', '4', '4', '1'), ('1', '4', '4', '1', '4'), ('4', '1', '4', '1', '4'), ('4', '1', '1', '1', '4'), ('4', '4', '1', '1', '4'), ('1', '4', '1', '4', '4'), ('1', '1', '4', '1', '4'), ('4', '4', '1', '1', '1'), ('4', '1', '1', '4', '4'), ('1', '1', '1', '4', '4')])

Note**

First create all possible combination possible with '1' and '4'. Please note with the restriction of maximum N instances of particular integer, so in a set of K numbers if there are i instances of x then there is (K-i) instances of y for two numbers (x,y). In that case both i and x should be in the range [K-N,N].

Now the next step is to use a generator comprehension to create all possible iteration of all possible instances of the above set. I am using a set comprehension to remove any duplicate and also using generator to not store the intermediate duplicate results.

Upvotes: 4

mcdowella
mcdowella

Reputation: 19601

For small values of K I would count from 0 to 2^K - 1, skipping values where the binary representation has more than N 0s or more than N 1s, and then translate 0 bits to '1' and 1 bits to '4'.

For large values of K you could use backtracking search - 

PseudoCode (int N, int K, int num1s, int num4s, String sofar)
  if (num1s > K)
     return
  if (num4s > K)
     return
  length(sofar) == N
     print sofar
     return
  PseudoCode (N, K, num1s + 1, num4s, sofar + "1")
  PseudoCode (N, K, num1s, num4s + 1, sofar + "4")

Upvotes: 0

mathematical.coffee
mathematical.coffee

Reputation: 56915

This is one way to think about it, although I wonder at a more elegant solution:

Suppose N = 3 and K = 5 like above. Instead of your '1' and '4' I'm going to use a and b or else I'll confuse myself :P

Since each symbol (a or b) is only allowed to appear 3 times at most, it means we want to get all permutations of:

  • 2 as in a string of 5 bs
  • 3 as in a string of 5 bs

So we only need to find all permutations of {a,a,b,b,b} and {a,a,a,b,b}.

Generalising this, you only need to find permutations of {m lots of a, and (K-m) lots of b}, where m is in { K-N, K-N+1, K-N+2, ... N }.

One way to do this is:

  1. set N,K.
  2. Set m = K-N.
  3. Make a list filled with b of length K, call it x.
  4. Make a list of indices into x (i.e. 0,1,2,..,K-1), and find all subsets of length m into this. These will be where we place the as.
  5. Repeat for m = K-N, K-N+1, ... , N.

To do step 4, we use the module itertools, and in particular, itertools.combinations.

So:

import itertools

def notQuitePermutations(N,K,symbol1,symbol2):
    permutations = []
    base_perm = [symbol2]*K # step 3
    for m in range(K-N,N+1): # +1 so we *include* N
        # step 4: find m places to put symbol1 in.
        idxs = itertools.combinations(range(K),m)
        for idx in idxs:
            perm = base_perm[:] # make a copy of base_perm
            for i in idx:
                perm[i] = symbol1 # put symbol1 in.
            # add this permutation to the list
            permutations += [perm]
    return permutations

Then:

>>> notQuitePermutations(3,5,1,4)
[[1, 1, 4, 4, 4], [1, 4, 1, 4, 4], [1, 4, 4, 1, 4],....

Another alternative is to find all permutations of {m lots of symbol1, and (K-m) lots of symbol2}, using itertools.permutations. Except that you get duplicates there (since Python does permutations based off unique positions of elements, not unique values of elements). Then you need to filter them out afterwards, which could get expensive once K and N get large. That's why I chose the above approach, because it doesn't have the problem of duplicates.

Upvotes: 1

Related Questions