En utilisant la récursivité et les retours en arrière pour générer toutes les combinaisons possibles

Personnellement, je aller avec une simple solution itérative.

Vous représenter ensemble de nœuds comme un ensemble de bits. Si vous avez besoin de 5 nœuds alors 5 bits, chaque bit représentant un nœud spécifique. Si vous voulez que 3 de ces dans votre tupple ensuite, vous avez juste besoin de mettre 3 des bits et le suivi de leur emplacement.

Fondamentalement, c'est une simple variation sur le fonding de tous les différents sous-ensembles de nœuds de combinaisons. Où le classique de la mise en œuvre est de représenter l'ensemble de nœuds comme un entier. Chacun des bits de l'entier représente un nœud. L'ensemble vide est 0. Ensuite, vous avez juste incrémenter le nombre entier chaque nouvelle valeur est un nouvel ensemble de nœuds (la séquence de bits représentant l'ensemble des nœuds). Juste dans cette variante, vous assurez-vous qu'il y a toujours 3 nœuds.

Juste pour m'aider à penser, je commence avec les 3 premiers nœuds active { 4, 3, 2 }. Puis-je compter vers le bas. Mais il serait trivial de modifier ce nombre dans l'autre sens.

#include <boost/dynamic_bitset.hpp>
#include <iostream>
class TuppleSet
{
friend std::ostream& operator<<(std::ostream& stream, TuppleSet const& data);
boost::dynamic_bitset<> data;    //represents all the different nodes
std::vector<int>        bitpos;  //tracks the 'n' active nodes in the tupple
public:
TuppleSet(int nodes, int activeNodes)
: data(nodes)
, bitpos(activeNodes)
{
//Set up the active nodes as the top 'activeNodes' node positions.
for(int loop = 0;loop < activeNodes;++loop)
{
bitpos[loop]        = nodes-1-loop;
data[bitpos[loop]]  = 1;
}
}
bool next()
{
//Move to the next combination
int bottom  = shiftBits(bitpos.size()-1, 0);
//If it worked return true (otherwise false)
return bottom >= 0;
}
private:
//index is the bit we are moving. (index into bitpos)
//clearance is the number of bits below it we need to compensate for.
//
// [ 0, 1, 1, 1, 0 ]   =>    { 3, 2, 1 }
//            ^
//            The bottom bit is move down 1 (index => 2, clearance => 0)
// [ 0, 1, 1, 0, 1]    =>    { 3, 2, 0 }
//               ^
//            The bottom bit is moved down 1 (index => 2, clearance => 0)
//            This falls of the end
//         ^
//            So we move the next bit down one (index => 1, clearance => 1)
// [ 0, 1, 0, 1, 1]
//               ^
//            The bottom bit is moved down 1 (index => 2, clearance => 0)
//            This falls of the end
//            ^
//            So we move the next bit down one (index =>1, clearance => 1)
//            This does not have enough clearance to move down (as the bottom bit would fall off)
//     ^      So we move the next bit down one (index => 0, clearance => 2)
//[ 0, 0, 1, 1, 1] 
int shiftBits(int index, int clerance)
{
if (index == -1)
{   return -1;
}
if (bitpos[index] > clerance)
{
--bitpos[index];
}
else
{
int nextBit = shiftBits(index-1, clerance+1);
bitpos[index] = nextBit-1;
}
return bitpos[index];
}
};
std::ostream& operator<<(std::ostream& stream, TuppleSet const& data)
{
stream << "{ ";
std::vector<int>::const_iterator loop = data.bitpos.begin();
if (loop != data.bitpos.end())
{
stream << *loop;
++loop;
for(; loop != data.bitpos.end(); ++loop)
{
stream << ", " << *loop;
}
}
stream << " }";
return stream;
}

Principal est trivial:

int main()
{
TuppleSet   s(5,3);
do
{
std::cout << s << "\n";
}
while(s.next());
}

De sortie est:

{ 4, 3, 2 }
{ 4, 3, 1 }
{ 4, 3, 0 }
{ 4, 2, 1 }
{ 4, 2, 0 }
{ 4, 1, 0 }
{ 3, 2, 1 }
{ 3, 2, 0 }
{ 3, 1, 0 }
{ 2, 1, 0 }

Une version de shiftBits() à l'aide d'une boucle

    int shiftBits()
{
int bottom   = -1;
for(int loop = 0;loop < bitpos.size();++loop)
{
int index   = bitpos.size() - 1 - loop;
if (bitpos[index] > loop)
{
bottom = --bitpos[index];
for(int shuffle = loop-1; shuffle >= 0; --shuffle)
{
int index   = bitpos.size() - 1 - shuffle;
bottom = bitpos[index] = bitpos[index-1]  - 1;
}
break;
}
}
return bottom;
}

OriginalL'auteur Martin York