Er zijn n mensen genummerd van 1tot n. Ik moet een code schrijven die alle verschillende combinaties van Kmensen van deze nproduceert en print. Leg uit welk algoritme daarvoor is gebruikt.
Antwoord 1, autoriteit 100%
Ik neem aan dat je vraagt naar combinaties in combinatorische zin (dat wil zeggen dat de volgorde van elementen er niet toe doet, dus [1 2 3]is hetzelfde als [2 1 3]). Het idee is dan vrij eenvoudig, als je inductie / recursie begrijpt: om alle K-elementcombinaties te krijgen, kies je eerst het eerste element van een combinatie uit een bestaande set mensen, en dan “aaneenschakelen” dit initiële element met alle mogelijke combinaties van K-1mensen geproduceerd uit elementen die het initiële element opvolgen.
Als voorbeeld, laten we zeggen dat we alle combinaties van 3 personen willen nemen uit een set van 5 personen. Dan kunnen alle mogelijke combinaties van 3 personen uitgedrukt worden in termen van alle mogelijke combinaties van 2 personen:
comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }
Hier is C++ code die dit idee implementeert:
#include <iostream>
#include <vector>
using namespace std;
vector<int> people;
vector<int> combination;
void pretty_print(const vector<int>& v) {
static int count = 0;
cout << "combination no " << (++count) << ": [ ";
for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
cout << "] " << endl;
}
void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people[i]);
go(i+1, k-1);
combination.pop_back();
}
}
int main() {
int n = 5, k = 3;
for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);
return 0;
}
En hier is de uitvoer voor N = 5, K = 3:
combination no 1: [ 1 2 3 ]
combination no 2: [ 1 2 4 ]
combination no 3: [ 1 2 5 ]
combination no 4: [ 1 3 4 ]
combination no 5: [ 1 3 5 ]
combination no 6: [ 1 4 5 ]
combination no 7: [ 2 3 4 ]
combination no 8: [ 2 3 5 ]
combination no 9: [ 2 4 5 ]
combination no 10: [ 3 4 5 ]
Antwoord 2, autoriteit 87%
Van Rosetta-code
#include <algorithm>
#include <iostream>
#include <string>
void comb(int N, int K)
{
std::string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's
// print integers and permute bitmask
do {
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i]) std::cout << " " << i;
}
std::cout << std::endl;
} while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}
int main()
{
comb(5, 3);
}
uitvoer
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
Analyse en idee
Het hele punt is om te spelen met de binaire representatie van getallen
het getal 7in binair getal is bijvoorbeeld 0111
Dus deze binaire representatie kan ook als zodanig worden gezien als een toewijzingslijst:
Voor elke bit ials de bit is ingesteld (dwz 1) betekent dat het ide item is toegewezen, anders niet.
p>
Vervolgens door simpelweg een lijst met opeenvolgende binaire getallen te berekenen en de binaire representatie te gebruiken (wat erg snel kan zijn), ontstaat een algoritme om alle combinaties van Nover kte berekenen .
De sorteringaan het einde (van sommige implementaties) is niet nodig. Het is slechts een manier om het resultaat deterministisch te normaliseren, d.w.z. voor dezelfde getallen (N, K) en hetzelfde algoritme wordt dezelfde volgordevan combinaties geretourneerd
Voor meer informatie over getalrepresentaties en hun relatie tot combinaties, permutaties, machtenverzamelingen (en andere interessante dingen), kijk eens op Combinatorisch nummersysteem, Factoriaal nummersysteem
PS:Misschien wil je mijn combinatorisch raamwerk Abacusdat vele soorten combinatorische objecten efficiënt berekent en zijn routines (oorspronkelijk in JavaScript) kunnen gemakkelijk worden aangepast aan vele andere talen.
Antwoord 3, autoriteit 20%
Als het nummer van de set binnen 32, 64 of een machineeigen primitieve grootte zou zijn, dan kunt u dit doen met een eenvoudige bitmanipulatie.
template<typename T>
void combo(const T& c, int k)
{
int n = c.size();
int combo = (1 << k) - 1; // k bit sets
while (combo < 1<<n) {
pretty_print(c, combo);
int x = combo & -combo;
int y = combo + x;
int z = (combo & ~y);
combo = z / x;
combo >>= 1;
combo |= y;
}
}
dit voorbeeld roept de functie pretty_print() aan volgens de woordenboekvolgorde.
Bijvoorbeeld. U wilt 6C3 hebben en ervan uitgaande dat de huidige ‘combo’ 010110 is.
Het is duidelijk dat de volgende combo 011001 MOET zijn.
011001 is:
010000 | 001000 | 000001
010000: continu 1s van LSB-zijde verwijderd.
001000: stel 1 in op de volgende van continu 1s van de LSB-zijde.
000001: continu 1s van LSB naar rechts verschoven en LSB-bit verwijderen.
int x = combo & -combo;
dit levert de laagste 1 op.
int y = combo + x;
dit elimineert continu 1s van de LSB-kant en zet 1 op de volgende (in het bovenstaande geval 010000 | 001000)
int z = (combo & ~y)
dit geeft je de continue 1s van de LSB-kant (000110).
combo = z / x;
combo >> =1;
dit is voor ‘continu 1s van LSB naar rechts verschoven en LSB-bit verwijderen’.
Dus de laatste taak is OR y naar het bovenstaande.
combo |= y;
Een eenvoudig concreet voorbeeld:
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void pretty_print(const T& c, int combo)
{
int n = c.size();
for (int i = 0; i < n; ++i) {
if ((combo >> i) & 1)
cout << c[i] << ' ';
}
cout << endl;
}
template<typename T>
void combo(const T& c, int k)
{
int n = c.size();
int combo = (1 << k) - 1; // k bit sets
while (combo < 1<<n) {
pretty_print(c, combo);
int x = combo & -combo;
int y = combo + x;
int z = (combo & ~y);
combo = z / x;
combo >>= 1;
combo |= y;
}
}
int main()
{
vector<char> c0 = {'1', '2', '3', '4', '5'};
combo(c0, 3);
vector<char> c1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
combo(c1, 4);
return 0;
}
resultaat:
1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
a b c d
a b c e
a b d e
a c d e
b c d e
a b c f
a b d f
a c d f
b c d f
a b e f
a c e f
b c e f
a d e f
b d e f
c d e f
a b c g
a b d g
a c d g
b c d g
a b e g
a c e g
b c e g
a d e g
b d e g
c d e g
a b f g
a c f g
b c f g
a d f g
b d f g
c d f g
a e f g
b e f g
c e f g
d e f g
Antwoord 4, autoriteit 9%
In Python wordt dit geïmplementeerd als itertools.combinations
https://docs.python.org/2/library /itertools.html#itertools.combinations
In C++ zou zo’n combinatiefunctie kunnen worden geïmplementeerd op basis van de permutatiefunctie.
Het basisidee is om een vector van grootte n te gebruiken, en alleen k item op 1 binnenin te zetten, dan kunnen alle combinaties van nchoosek worden verkregen door de k items in elke permutatie te verzamelen.
Hoewel het misschien niet de meest efficiënte manier is, is er veel ruimte nodig, omdat combinatie meestal een zeer groot aantal is. Het is beter om te worden geïmplementeerd als een generator of om werkende codes in do_sth() te plaatsen.
Codevoorbeeld:
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main(void) {
int n=5, k=3;
// vector<vector<int> > combinations;
vector<int> selected;
vector<int> selector(n);
fill(selector.begin(), selector.begin() + k, 1);
do {
for (int i = 0; i < n; i++) {
if (selector[i]) {
selected.push_back(i);
}
}
// combinations.push_back(selected);
do_sth(selected);
copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, " "));
cout << endl;
selected.clear();
}
while (prev_permutation(selector.begin(), selector.end()));
return 0;
}
en de uitvoer is
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
Deze oplossing is eigenlijk een duplicaat met
Combinaties genereren in c++
Antwoord 5, autoriteit 3%
Hier is een algoritme dat ik heb bedacht om dit probleem op te lossen. Je zou het moeten kunnen aanpassen om met je code te werken.
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
Je kunt een uitleg zien van hoe het werkt hier.
Antwoord 6
Ik heb een klasse in C# geschreven om algemene functies af te handelen voor het werken met de binominale coëfficiënt, het type probleem waar uw probleem onder valt. Het voert de volgende taken uit:
-
Geef alle K-indexen op in een mooi formaat voor elke N kies K naar een bestand. De K-indexen kunnen worden vervangen door meer beschrijvende tekenreeksen of letters. Deze methode maakt het oplossen van dit soort problemen vrij triviaal.
-
Converteert de K-indexen naar de juiste index van een item in de gesorteerde binominale coëfficiëntentabel. Deze techniek is veel sneller dan oudere gepubliceerde technieken die afhankelijk zijn van iteratie. Het doet dit door een wiskundige eigenschap te gebruiken die inherent is aan de driehoek van Pascal. Mijn paper gaat hierover. Ik geloof dat ik de eerste ben die deze techniek ontdekt en publiceert.
-
Converteert de index in een gesorteerde binomiale coëfficiënttabel met de overeenkomstige K-indexen. Ik geloof dat het ook sneller is dan de andere oplossingen.
-
gebruikt Mark Dominus methode om de binomiale coëfficiënt te berekenen, wat veel is minder kans om te overlopen en met grotere aantallen werkt.
-
De klasse is geschreven in .NET C # en biedt een manier om de objecten met betrekking tot het probleem (indien aanwezig) te beheren door een generieke lijst te gebruiken. De constructeur van deze klasse neemt een Bool-waarde genaamd Dordatable dat wanneer True een generieke lijst zal maken om de te beheert objecten te houden. Als deze waarde onjuist is, maakt het de tabel niet. De tabel hoeft niet te worden gemaakt om de 4 bovenstaande methoden uit te voeren. Accessor-methoden zijn aanwezig om toegang te krijgen tot de tabel.
-
Er is een bijbehorende testklasse die laat zien hoe u de klasse en de methoden kunt gebruiken. Het is uitgebreid getest met 2 gevallen en er zijn geen bekende bugs.
om over deze klas te lezen en de code te downloaden, zie het tikken van de binomiale coëffieicent .
Het zou vrij recht naar voren moeten zijn om de klasse naar C++ te haven.
De oplossing voor uw probleem omvat het genereren van de K-indexen voor elke N Kies K-zaak. Bijvoorbeeld:
int NumPeople = 10;
int N = TotalColumns;
// Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
int[] KIndexes = new int[K];
BC.OutputKIndexes(FileName, DispChars, "", " ", 60, false);
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
// Get the k-indexes for this combination, which in this case
// are the indexes to each person in the problem set.
BC.GetKIndexes(Loop, KIndexes);
// Do whatever processing that needs to be done with the indicies in KIndexes.
...
}
}
De methode UitgangSpindexes kan ook worden gebruikt om de K-indexen naar een bestand uit te voeren, maar het zal een ander bestand gebruiken voor elke n kies k-zaak.
Antwoord 7
U kunt de “COUNT_EACH_COMBINATION” en “FORE_EACH_COMBINATION” gebruiken van de combinaties Bibliotheek van Howard Hinnant om alle combinaties te genereren voor Take K van n.
#include <vector>
#include "combinations.h"
std::vector<std::vector<u_int8_t> >
combinationsNoRepetitionAndOrderDoesNotMatter (long int subsetSize, std::vector<uint8_t> setOfNumbers)
{
std::vector<std::vector<u_int8_t> > subsets{};
subsets.reserve (count_each_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize, setOfNumbers.end ()));
for_each_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize, setOfNumbers.end (), [&subsets] (auto first, auto last) {
subsets.push_back (std::vector<uint8_t>{ first, last });
return false;
});
return subsets;
}
int main(){
combinationsNoRepetitionAndOrderDoesNotMatter (6, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 });
}
Benchmark op een Intel (R) Core (TM) i5-8600K CPU @ 3.60GHz:
g ++
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
combinations no repetition and
order does not matter 6 from 36 100 1 10.2829 s
92.5451 ms 92.3971 ms 92.9411 ms
1.15617 ms 532.604 us 2.48342 ms
clang++
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
combinations no repetition and
order does not matter 6 from 36 100 1 11.0786 s
88.1275 ms 87.8212 ms 89.3204 ms
2.82107 ms 400.665 us 6.67526 ms
Antwoord 8
Achter de onderstaande link staat een generiek C#-antwoord op dit probleem: Hoe alle combinaties op te maken uit een lijst met objecten. Je kunt de resultaten vrij gemakkelijk beperken tot de lengte van k.
https://stackoverflow.com/a/40417765/2613458
Antwoord 9
Het kan ook worden gedaan met behulp van backtracking door een bezochte array te onderhouden.
void foo(vector<vector<int> > &s,vector<int> &data,int go,int k,vector<int> &vis,int tot)
{
vis[go]=1;
data.push_back(go);
if(data.size()==k)
{
s.push_back(data);
vis[go]=0;
data.pop_back();
return;
}
for(int i=go+1;i<=tot;++i)
{
if(!vis[i])
{
foo(s,data,i,k,vis,tot);
}
}
vis[go]=0;
data.pop_back();
}
vector<vector<int> > Solution::combine(int n, int k) {
vector<int> data;
vector<int> vis(n+1,0);
vector<vector<int> > sol;
for(int i=1;i<=n;++i)
{
for(int i=1;i<=n;++i) vis[i]=0;
foo(sol,data,i,k,vis,n);
}
return sol;
}
Antwoord 10
Ik dacht dat mijn eenvoudige “alle mogelijke combinatiegenerator” iemand zou kunnen helpen, ik denk dat het een heel goed voorbeeld is om iets groters en beters te bouwen
je kunt N(tekens)veranderen in wat je maar wilt door gewoon verwijderen/toevoegen uit stringarray(je kunt veranderen het ook naar int).Het huidige aantal tekens is 36
je kunt ook K(grootte van de gegenereerde combinaties)veranderen door gewoon meer loops toe te voegen, voor elk element moet er één zijn extra lus. Huidige maat is 4
#include<iostream>
using namespace std;
int main() {
string num[] = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z" };
for (int i1 = 0; i1 < sizeof(num)/sizeof(string); i1++) {
for (int i2 = 0; i2 < sizeof(num)/sizeof(string); i2++) {
for (int i3 = 0; i3 < sizeof(num)/sizeof(string); i3++) {
for (int i4 = 0; i4 < sizeof(num)/sizeof(string); i4++) {
cout << num[i1] << num[i2] << num[i3] << num[i4] << endl;
}
}
}
}}
Resultaat
0: A A A
1: B A A
2: C A A
3: A B A
4: B B A
5: C B A
6: A C A
7: B C A
8: C C A
9: A A B
...
Houd er rekening mee dat het aantal combinaties belachelijk kan zijn.
–UPDATE–
een betere manier om alle mogelijke combinaties te genereren zou zijn met deze code, die eenvoudig kan worden aangepast en geconfigureerd in het gedeelte ‘variabelen’ van de code.
#include<iostream>
#include<math.h>
int main() {
//VARIABLES
char chars[] = { 'A', 'B', 'C' };
int password[4]{0};
//SIZES OF VERIABLES
int chars_length = sizeof(chars) / sizeof(char);
int password_length = sizeof(password) / sizeof(int);
//CYCKLE TROUGH ALL OF THE COMBINATIONS
for (int i = 0; i < pow(chars_length, password_length); i++){
//CYCKLE TROUGH ALL OF THE VERIABLES IN ARRAY
for (int i2 = 0; i2 < password_length; i2++) {
//IF VERIABLE IN "PASSWORD" ARRAY IS THE LAST VERIABLE IN CHAR "CHARS" ARRRAY
if (password[i2] == chars_length) {
//THEN INCREMENT THE NEXT VERIABLE IN "PASSWORD" ARRAY
password[i2 + 1]++;
//AND RESET THE VERIABLE BACK TO ZERO
password[i2] = 0;
}}
//PRINT OUT FIRST COMBINATION
std::cout << i << ": ";
for (int i2 = 0; i2 < password_length; i2++) {
std::cout << chars[password[i2]] << " ";
}
std::cout << "\n";
//INCREMENT THE FIRST VERIABLE IN ARRAY
password[0]++;
}}
Antwoord 11
Om het vollediger te maken, behandelt het volgende antwoord het geval dat de dataset dubbele waarden bevat. De functie is dicht bij de stijl van std::next_permutation() geschreven, zodat het gemakkelijk te volgen is.
template< class RandomIt >
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
if (first == last || n_first == first || n_first == last)
{
return false;
}
RandomIt it_left = n_first;
--it_left;
RandomIt it_right = n_first;
bool reset = false;
while (true)
{
auto it = std::upper_bound(it_right, last, *it_left);
if (it != last)
{
std::iter_swap(it_left, it);
if (reset)
{
++it_left;
it_right = it;
++it_right;
std::size_t left_len = std::distance(it_left, n_first);
std::size_t right_len = std::distance(it_right, last);
if (left_len < right_len)
{
std::swap_ranges(it_left, n_first, it_right);
std::rotate(it_right, it_right+left_len, last);
}
else
{
std::swap_ranges(it_right, last, it_left);
std::rotate(it_left, it_left+right_len, n_first);
}
}
return true;
}
else
{
reset = true;
if (it_left == first)
{
break;
}
--it_left;
it_right = n_first;
}
}
return false;
}
De volledige dataset wordt weergegeven in het bereik [first, last). De huidige combinatie wordt weergegeven in het bereik [first, n_first) en het bereik [n_first, last] bevat de complementaire set van de huidige combinatie.
Omdat een combinatie niet relevant is voor de volgorde, worden [first, n_first) en [n_first, last) in oplopende volgorde gehouden om duplicatie te voorkomen.
Het algoritme werkt door de laatste waarde A aan de linkerkant te verhogen door te wisselen met de eerste waarde B aan de rechterkant die groter is dan A. Na het omwisselen zijn beide zijden nog steeds geordend. Als zo’n waarde B aan de rechterkant niet bestaat, beginnen we te overwegen de voorlaatste aan de linkerkant te verhogen totdat alle waarden aan de linkerkant niet minder zijn dan aan de rechterkant.
Een voorbeeld van het tekenen van 2 elementen uit een set met de volgende code:
std::vector<int> seq = {1, 1, 2, 2, 3, 4, 5};
do
{
for (int x : seq)
{
std::cout << x << " ";
}
std::cout << "\n";
} while (next_combination(seq.begin(), seq.begin()+2, seq.end()));
geeft:
1 1 2 2 3 4 5
1 2 1 2 3 4 5
1 3 1 2 2 4 5
1 4 1 2 2 3 5
1 5 1 2 2 3 4
2 2 1 1 3 4 5
2 3 1 1 2 4 5
2 4 1 1 2 3 5
2 5 1 1 2 3 4
3 4 1 1 2 2 5
3 5 1 1 2 2 4
4 5 1 1 2 2 3
Het is triviaal om indien nodig de eerste twee elementen op te halen als het combinatieresultaat.
Antwoord 12
Het basisidee van deze oplossing is om de manier na te bootsen waarop je alle combinaties opsomt zonder herhalingen met de hand op de middelbare school. Laat com List[int] van lengte k zijn en nums is List[int] de gegeven n items, waarbij n >= k.
Het idee is als volgt:
for x[0] in nums[0,...,n-1]
for x[1] in nums[idx_of_x[0] + 1,..,n-1]
for x[2] in nums [idx_of_x[1] + 1,...,n-1]
..........
for x[k-1] in nums [idx_of_x[k-2]+1, ..,n-1]
Het is duidelijk dat k en n variabele argumenten zijn, waardoor het onmogelijk is om expliciete meerdere geneste for-loops te schrijven. Dit is waar de recursie komt om het probleem te redden.
Statement len(com) + len(nums[i:]) >= kcontroleert of de resterende niet-bezochte voorwaartse lijst met items k iitems kan opleveren. Met vooruit bedoel ik dat je de getallen niet achteruit moet lopen om de herhaalde combinatie te vermijden, die uit dezelfde set items bestaat maar in een andere volgorde. Anders gezegd, in deze verschillende volgordes, kunnen we de volgorde kiezen waarin deze items in de lijst verschijnen door de lijst naar voren te scannen. Belangrijker is dat deze testclausule intern de recursieboom snoeit, zodat deze alleen n choose krecursieve aanroepen bevat. Daarom is de looptijd O(n choose k).
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
assert 1 <= n <= 20
assert 1 <= k <= n
com_sets = []
self._combine_recurse(k, list(range(1, n+1)), [], com_sets)
return com_sets
def _combine_recurse(self, k: int, nums: List[int], com: List[int], com_set: List[List[int]]):
"""
O(C_n^k)
"""
if len(com) < k:
for i in range(len(nums)):
# Once again, don't com.append() since com should not be global!
if len(com) + len(nums[i:]) >= k:
self._combine_recurse(k, nums[i+1:], com + [nums[i]], com_set)
else:
if len(com) == k:
com_set.append(com)
print(com)
sol = Solution()
sol.combine(5, 3)
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
Antwoord 13
Deze sjabloonfunctie werkt met de vector van elk type als invoer.
Combinaties worden geretourneerd als een vector van vectoren.
/*
* Function return all possible combinations of k elements from N-size inputVector.
* The result is returned as a vector of k-long vectors containing all combinations.
*/
template<typename T> std::vector<std::vector<T>> getAllCombinations(const std::vector<T>& inputVector, int k)
{
std::vector<std::vector<T>> combinations;
std::vector<int> selector(inputVector.size());
std::fill(selector.begin(), selector.begin() + k, 1);
do {
std::vector<int> selectedIds;
std::vector<T> selectedVectorElements;
for (int i = 0; i < inputVector.size(); i++) {
if (selector[i]) {
selectedIds.push_back(i);
}
}
for (auto& id : selectedIds) {
selectedVectorElements.push_back(inputVector[id]);
}
combinations.push_back(selectedVectorElements);
} while (std::prev_permutation(selector.begin(), selector.end()));
return combinations;
}