Permutations of Varying Size

Question

I'm trying to write a function in PHP that gets all permutations of all possible sizes. I think an example would be the best way to start off:

$my_array = array(1,1,2,3);

Possible permutations of varying size:

1
1 // * See Note
2
3
1,1
1,2
1,3
// And so forth, for all the sets of size 2
1,1,2
1,1,3
1,2,1
// And so forth, for all the sets of size 3
1,1,2,3
1,1,3,2
// And so forth, for all the sets of size 4

Note: I don't care if there's a duplicate or not. For the purposes of this example, all future duplicates have been omitted.

What I have so far in PHP:

function getPermutations($my_array){

$permutation_length = 1;
$keep_going = true;    

while($keep_going){
    while($there_are_still_permutations_with_this_length){
        // Generate the next permutation and return it into an array
        // Of course, the actual important part of the code is what I'm having trouble with.
    }
    $permutation_length++;
    if($permutation_length>count($my_array)){
        $keep_going = false;
    }
    else{
        $keep_going = true;
        }
}

return $return_array;

}

The closest thing I can think of is shuffling the array, picking the first n elements, seeing if it's already in the results array, and if it's not, add it in, and then stop when there are mathematically no more possible permutations for that length. But it's ugly and resource-inefficient.

Any pseudocode algorithms would be greatly appreciated.

---

Also, for super-duper (worthless) bonus points, is there a way to get just 1 permutation with the function but make it so that it doesn't have to recalculate all previous permutations to get the next?

For example, I pass it a parameter 3, which means it's already done 3 permutations, and it just generates number 4 without redoing the previous 3? (Passing it the parameter is not necessary, it could keep track in a global or static).

The reason I ask this is because as the array grows, so does the number of possible combinations. Suffice it to say that one small data set with only a dozen elements grows quickly into the trillions of possible combinations and I don't want to task PHP with holding trillions of permutations in its memory at once.

Answer 1

Sorry no php code, but I can give you an algorithm.

It can be done with small amounts of memory and since you don't care about dupes, the code will be simple too.

First: Generate all possible subsets.

If you view the subset as a bit vector, you can see that there is a 1-1 correspondence to a set and a binary number.

So if your array had 12 elements, you will have 2^12 subsets (including empty set).

So to generate a subset, you start with 0 and keep incrementing till you reach 2^12. At each stage you read the set bits in the number to get the appropriate subset from the array.

Once you get one subset, you can now run through its permutations.

The next permutation (of the array indices, not the elements themselves) can be generated in lexicographic order like here: http://www.de-brauwer.be/wiki/wikka.php?wakka=Permutations and can be done with minimal memory.

You should be able to combine these two to give your-self a next_permutation function. Instead of passing in numbers, you could pass in an array of 12 elements which contains the previous permutation, plus possibly some more info (little memory again) of whether you need to go to the next subset etc.

You should actually be able to find very fast algorithms which use minimal memory, provide a next_permutation type feature and do not generate dupes: Search the web for multiset permutation/combination generation.

Hope that helps. Good luck!

Answer 2

The best set of functions I've come up with was the one provided by some user at the comments of the shuffle function on php.net Here is the link It works pretty good.

Hope it's useful.

Answer 3

The problem seems to be trying to give an index to every permutation and having a constant access time. I cannot think of a constant time algorithm, but maybe you can improve this one to be so. This algorithm has a time complexity of O(n) where n is the length of your set. The space complexity should be reducible to O(1).

Assume our set is 1,1,2,3 and we want the 10th permutation. Also, note that we will index each element of the set from 0 to 3. Going by your order, this means the single element permutations come first, then the two element, and so on. We are going to subtract from the number 10 until we can completely determine the 10th permutation.

First up are the single element permutations. There are 4 of those, so we can view this as subtracting one four times from 10. We are left with 6, so clearly we need to start considering the two element permutations. There are 12 of these, and we can view this as subtracting three up to four times from 6. We discover that the second time we subtract 3, we are left with 0. This means the indexes of our permutation must be 2 (because we subtracted 3 twice) and 0, because 0 is the remainder. Therefore, our permutation must be 2,1.

Division and modulus may help you.

If we were looking for the 12th permutation, we would run into the case where we have a remainder of 2. Depending on your desired behavior, the permutation 2,2 might not be valid. Getting around this is very simple, however, as we can trivially detect that the indexes 2 and 2 (not to be confused with the element) are the same, so the second one should be bumped to 3. Thus the 12th permutation can trivially be calculated as 2,3.

The biggest confusion right now is that the indexes and the element values happen to match up. I hope my algorithm explanation is not too confusing because of that. If it is, I will use a set other than your example and reword things.

Answer 4

Inputs: Permutation index k, indexed set S.

Pseudocode:

L = {S_1}
for i = 2 to |S| do
 Insert S_i before L_{k % i}
 k <- k / i
loop
return L

This algorithm can also be easily modified to work with duplicates.