3

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. :)

Improve this question

4 Answers 4

Reset to default
4

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.

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

7 Comments

Hi, I have tried this and I get an error saying 's' is not defined. Also based on your output, 4 always appear at most 2 times only, permutation like this -> (4, 4, 4, 1, 1), should also be considered. So basically your output is not complete.. Thanks for your effort..
@Manie, There was a small problem which I fixed it. You should now get permutations similar to one you mentioned. Btw, what version of python are you using? Can you provide the full stack trace? I don't see a reason why this should not work. Just try it out and if it fail's please provide the stack trace.
hi, i got it, what I did is to re-arrange the set(x for x in itertools.permutations(s) for s in src) to set(x for s in src for x in itertools.permutations(s)), to get the correct result.
Yes, that was my problem. You can check the fix above. Also there was a problem when comprehending src which is now fixed.
@Manie, Btw, if this solution work's you may want to select this answer as an accepted answer
|
2

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)

Improve this answer

Comments

1

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.

Improve this answer

3 Comments

urgh, ignore this answer, @Abhijit's is so much nicer :P. I didn't know about set.
thanks for a very nice explanation. Anyway using your code I tried something like this len(notQuitePermutations(50,100,1,5)), and I get a "MemoryError" so I guess it's not efficient for larger values. What I want is an efficient algorithm.
Nope, don't ignore this, it's vastly more efficient for larger N and K.
0

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")
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.