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
