CODEWITHSUNDEEP
algorithmpermutation
kmd12
kmd12

Reputation: 115

Algorithm to generate all permutations of different sizes of a group of integers?

Let's say I have an array of integers, for example [3,4,2,7,8,5]

How would I generate different sized permutations from that array?

Like get ALL possible pairs of 2, or ALL possible sets of 3? of 4?

I'd like to be able to do this very quickly.

Upvotes: 0

Views: 2336

Answers (2)

AnT stands with Russia
AnT stands with Russia

Reputation: 320777

You can use any algorithm (like well-known Narayana algorithm) to generate all permutations of size N.

Now, if in this total sequence of permutations you consider only permutations with prefix (a1, a2, ..., ak) where a1 < a2 < ... < ak, then the tail portions of all such permutations will form a sequence of all possible permutations of length N - k.

That way by doing a single pass through all permutations of length N you can generate all permutations of length N and shorter.

Here's what a C++ implementation might look like

#include <iostream>
#include <algorithm>
#include <iterator>

int main() 
{
  int a[] = { 2, 3, 4, 5, 7, 8 };

  do
  {
    for (auto ite = std::begin(a); ite != std::end(a); ++ite)
      if (std::is_sorted(std::begin(a), ite))
      {
        std::copy(ite, std::end(a), std::ostream_iterator<int>(std::cout));
        std::cout << std::endl;
      }

  } while (std::next_permutation(std::begin(a), std::end(a)));
}

(I took the liberty of pre-sorting your input set.)

The above is obviously not optimal, since consecutive invocations of std::is_sorted inside the for cycle will repetitively re-scan/re-check what has already been checked on the previous iteration. But again, this implementation is intended to serve illustrative purposes only.

Now the question is whether you are happy with the order in which these permutations are generated. The above approach does not group them by length.

Alternatively, you can iterate through all possible combinations, and then just generate all possible permutations for each combination.

Upvotes: 1

John Coleman
John Coleman

Reputation: 52008

For a language-agnostic approach from first principles: enumerate all subsets of size k (for k = 2, ..., n, where n is the size of the array). The Wikipedia article on combinations has a section on their enumeration. For each enumerated subset use the Johnson-Trotter algorithm for enumerating the permutations of it. The total number of such permutations gets very large very quick. For example, with just 10 items there are 9,864,090

Many languages will have library support. For example, it is a trivial programming exercise in Python (using its itertools module). Here is a generator for producing such permutations:

import itertools

def allPermutations(items):
    n = len(items)
    for k in range(2,n+1):
        for combo in itertools.combinations(items,k):
            for perm in itertools.permutations(combo):
                yield perm

For example, list(allPermutations([3,4,2,7,8,5])) evaluates to the list of all 1950 such permutations drawn from [3,4,2,7,8,5].

Upvotes: 1

Related Questions