All permutations of size N and N is not necessarily equal to size of array

Question

I have a vector of strings with values {"Soa", "8", "m", "4", "8"}

I would like to print all permutations without repetitions (but duplicates allowed like "8" in vector above) for specified size n from array of size k. I have searched for solution to this but can't find any for this case.

Code at the moment is:

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>

int main()
{
    std::vector<std::string> arr = { "Soa", "4", "m", "8", "8" };
    std::sort(arr.begin(), arr.end());


        do {
            for(auto& i: arr)
                std::cout << i;

            std::cout << '\n';
        } while(std::next_permutation(arr.begin(), arr.end()));
}

This code prints all permutations for size of vector only (n=k), so it prints what I need but for n=5. What I would like is to specify n, so for example for n=2 to generate those permutations (order in which they are printed dosen't matter):

48
4Soa
4m
84
88
8Soa
8m
Soa4
Soa8
Soam
m4
m8
mSoa

EDIT: Solution linked by Nathan dosen't work, it treats 84 same as 48. Still looking for solution.

related/dupe, I do not think it excludes duplicates: http://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n — NathanOliver, May 18 '17 at 16:43
@Trailo They way to fix that is to store the results in a `std::set`. That will make sure you only get the unique permutations. — NathanOliver, May 18 '17 at 16:53
@NathanOliver The problem is that I will need to generate around 50 GB of those strings, much more than I have ram for it to keep in std::set. — Trailo, May 18 '17 at 16:56
@MBo I will try to get password for my bitcoin wallet that I forgot. I have a list of strings that I could used but I don't remember which positions in password they had, I remember that I only used once every string, but I could use numbers twice (that's why the duplicates). — Trailo, May 18 '17 at 17:05
@Trailo You could keep a set of string hashes, under the assumption that there will be no hash collisions. With a suitably small hash, you could save a decent amount of memory remembering duplicates. — cdhowie, May 18 '17 at 17:17
@NathanOliver Hm solution that you linked dosen't work. This is the output from k=2: 48 4Soa 4m 88 8Soa 8m Soam — Trailo, May 18 '17 at 17:38
In order to handle duplicates you could replace the strings by e.g. std::pair> and use (0,"8") and (1,"8") for the two strings, and ignore all permutations where (1,"8") occurs but is not after (0,"8") - that way you only get one output for duplicates. It is a bit wasteful - but not that slow and not using 50GB. — Hans Olsson, May 18 '17 at 17:40
@MBo Yes, this is a viable possiblity, but I need working code first, linked example is not a solution to this case. — Trailo, May 18 '17 at 17:40
Use next-permutation but only output the first 2 of every 6th result — M.M, May 19 '17 at 02:29
@Trailo You were right, my answer was not very useful, essentially it could have be replaced by `std::next_permutation`, so I deleted it. — Gert Wollny, May 19 '17 at 08:07
@M.M: The repeated values make things less regular. There ar different numbers of permuons with a given prefix depending on how many repeated values there are in the suffix. — rici, May 19 '17 at 13:43

score 1 · Accepted Answer · edited May 23 '17 at 12:26

This simple function is not optimal in execution time, but it's reasonably fast and is definitely efficient in programmer time. It constructs partial permutations by cycling through permutations but skipping permutations which don't change the k-element prefix. The vector must be sorted at the beginning; otherwise things will break horribly.

template<typename BidiIt>
bool next_partial_permutation(BidiIt first, BidiIt middle, BidiIt last) {
  std::reverse(middle, last);
  return std::next_permutation(first, last);
}

The function depends on the fact that next_permutation generates permutations in lexicographically increasing order. So it can go directly from the first permutation with a given k-prefix to the last permutation with that prefix simply by reversing the vector starting at position k.

(The first permutation with a given k-prefix has the elements starting at position k sorted; the last one has those elements sorted in reverse order; so reversing those elements means that the next call to next_permutation will produce the next prefix.)

The function was copy-pasted from this answer but I don't think the questions similar enough to qualify as a duplicate.

Here's an example of how to use it. The program should be provided with the value of k as its first command-line argument, followed by the n elements of the vector. (It sorts the vector before starting so you don't need to ensure the command-line arguments are sorted.)

int main(int argc, char** argv) {
    size_t k = std::atoi(argv[1]);
    std::vector<std::string> words(argv + 2, argv + argc);
    std::sort(words.begin(), words.end());
    do {
        for (size_t i = 0; i < k; ++i) std::cout << words[i];
        std::cout << '\n';
    } while (next_partial_permutation(words.begin(), words.begin() + k, words.end()));
    return 0;
}

Example output (live on coliru)

$ ./a.out 2 "Soa" "8" "m" "4" "8"
48
4Soa
4m
84
88
8Soa
8m
Soa4
Soa8
Soam
m4
m8
mSoa

All permutations of size N and N is not necessarily equal to size of array

1 Answers1