1
$\begingroup$

Heap's Algorithm enumerates the permutations of a set of N objects. It's described as:

  • Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.
  • Apply the following steps n−1 times. Increment counter i=1 after each iteration.
    • Swap element in position n with one of the other elements in the following way.
      • If n is odd, swap elements in positions 1 and n
      • If n is even, swap elements in position i and n
    • Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.

How can Heap's Algorithm be used to generate the k-permutations of N objects? That is, given a set of N objects, enumerate the ordered selection of k items from the N objects. How would the above algorithm be changed?

$\endgroup$

2 Answers 2

1
$\begingroup$

Yes, and the idea behind the modification is fairly straightforward.

Using a C-like notation, this is Heap's algorithm:

void
generate(int k)
{
    if (k == 1) {
        output(A[0..N-1]);
        return;
    }

    generate(k-1);
    for (int i = 0; i < k-1; ++i) {
        if (k % 2 == 0) {
            swap(A[i], A[k-1]);
        }
        else {
            swap(A[0], A[k-1]);
        }
        generate(k-1);
    }
}

generate(N);

This is the order that Heap's method produces all the permutations for $N=4$, say:

0 1 2 3
1 0 2 3
2 0 1 3
0 2 1 3
1 2 0 3
2 1 0 3
3 1 0 2
1 3 0 2
0 3 1 2
3 0 1 2
1 0 3 2
0 1 3 2
0 2 3 1
2 0 3 1
3 0 2 1
0 3 2 1
2 3 0 1
3 2 0 1
3 2 1 0
2 3 1 0
1 3 2 0
3 1 2 0
2 1 3 0
1 2 3 0

If you output the last $K$ digits for each permutation:

output(A[N-K..N-1]);

Then the output will be all $K$-permutations, with each permutation repeated exactly $K!$ times. For example, setting $N=4$ and $K=2$:

2 3
2 3
1 3
1 3
0 3
0 3
etc

To avoid the duplicates, therefore, you just need to skip to the last permutation in the group, which turns out to be a single swap if N-K is odd, but a slightly more complex permutation if N-K is even.

/* NOTE: The original version of this code did not get
   the even case correct. */
void
generate(int k)
{
    if (k == N-K) {
        output(A[N-K..N-1]);
        if (N > K + 1) {
            if (N-K is odd or K == 2) {
                swap(A[0],A[N-K-1]);
            }
            else {
                a0 = A[0];
                ank3 = A[N-K-3];
                ank2 = A[N-K-2];
                ank1 = A[N-K-1];
                for (int j = nmk-3; j > 1; --j) {
                    A[j] = A[j-1];
                }
                A[0] = ank3;
                A[1] = ank2;
                A[N-K-2] = ank1;
                A[N-K-1] = a0;
            }
        }
        return;
    }

    /* The code from here on is unchanged. */
    generate(k-1);
    for (int i = 0; i < k-1; ++i) {
        if (k is even) {
            swap(A[i], A[k-1]);
        }
        else {
            swap(A[0], A[k-1]);
        }
        generate(k-1);
    }
}

generate(N);
$\endgroup$
3
  • $\begingroup$ Thanks Pseudonym. Why does the single swap eliminate the duplicates? $\endgroup$
    – Ana
    Commented Aug 11, 2023 at 8:34
  • 1
    $\begingroup$ The above solution does not seem to work. P(N=8, K=4) = 1680 and the solution returns 1680 values, but only 515 unique values. They should all be unique. It seems to only return incorrect values with even K. Would you be able to provide working code? $\endgroup$
    – Ana
    Commented Aug 11, 2023 at 22:17
  • $\begingroup$ Yes, sorry, this is a bug. $\endgroup$
    – Pseudonym
    Commented Aug 12, 2023 at 2:11
0
$\begingroup$

by calling the original heap's algorithm generate(k,A), we expect it to print all permutations of $A[1:k]$ and $A$ will be rotated to the right $1$ unit if its size is even, else it'll be unaltered.

I've no idea how to generate k-permutations of N objects by directly changing heap's algo because by changing what we expect generate(k,A) to do we're changing the whole recurrence tree, ie. we may need to clearly re-specify each of the divide, conquer and combine step.

but still below is a more straightforward way to generate k-permutations of N objects (specifically the numbers $1,...,n$, it can be easily modified to permute other objects by treating $1,...,n$ as array indices) that make use of heap's algorithm. While it doesn't "directly modify" the heap's algorithm, it may give you some idea on how to do so.

basically, by calling k_perm_of_n(k,n) it prints all $k!$ permutations for each of the $\binom{n}{k}$ $k$-combinations of the set $\{1,...,n\}$. The only overhead is the rotation/copying of the array modified by heap's algorithm.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

//a is a k-combination of 1,...,n
//generates the next larger k-combination after 'a' according to lexicographic order (by mutating 'a')
//, e.g. {1,3,4} is larger than {1,2,4} compare from left to right entry-wise
//returns false when 'a' is already the largest combination, else returns true (and 'a' will be mutated)
bool next_combination(std::vector<int>& a, int n) {
    int k = (int)a.size();
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

//heap's algorithm
template<typename T>
void generate(int k,std::vector<T>&A){
    if(k==1){
        std::for_each(A.begin(),A.end(),[](const T&t){std::cout<<t<<' ';});
        std::cout<<std::endl;
    }
    else{
        generate(k-1,A);
        for(int i=0;i<k-1;++i){
            if(k%2==0)
                std::swap(A[i],A[k-1]);
            else
                std::swap(A[0],A[k-1]);
            generate(k-1,A);
        }
    }
}

//print all k permutations of 1,...,n
void k_perm_of_n(int k,int n){
    std::vector<int> a(k);
    std::iota(a.begin(),a.end(),1);//fill a with 1,...,k
    do{
        //for simplicity we just copy A to B as generate() may mutate the input array
        //alternatively you may rotate it back if A.size() is even
        std::vector<int>b(a);
        generate(k,b);//prints all permutations of this combination
    }while(next_combination(a,n));//move to next combination
}

int main(){
    k_perm_of_n(2,4);//print all 2-permutations in 1,...,4
}

the next_combination is from [1] and you may want to read [2], the heap's algorithm is from [3].

[1] Algorithms for Competitive Programming

[2] Combinatorial number system

[3]Heap's algorithm

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.