Permutation, Frage zu next_permutation

Hallo

Mit std::next_permutation kann ich ja einen array wie

{ 1, 2, 3 }

zu allen möglichen Permutationen transferieren der drei Werte permutieren:

{ 1, 2, 3 }
{ 1, 3, 2 }
{ 2, 1, 3 }
...

Wie bekomme ich es aber hin, zwar nur einen Array aus beispielsweise 3 Stellen zu haben, aber eine dieser Stellen nicht nur 3 verschiedene Werte sondern z.b. 10 verschiedene Wert haben kann?

{ 1, 2, 3 }
{ 1, 2, 4 }
{ 1, 2, 5 }
{ 1, 2, 6 }
{ 1, 2, 7 }
...
{ 7, 8, 3 }
...

Ich habe vor eine Zeichenkette mit beliebiger Länge und einem Charset ebenfalls beliebiger Länge auf diese Weise zu permutieren

"abcdefghijklmnopqrstuvwxyz"

jetzt will ich eine zeichenkette beliebiger länge alle möglichen kombinationen aus diesem charset zuweisen

"abc"
...
"fxd"
...
"jxz"

Jemand eine Idee wie man soetwas realisieren könnte?

CStoll

Du könntest per next_permutation() alle Permutationen von a..z durchlaufen lassen und dann jeweils die ersten n Elemente daraus rausgreifen (das erzeugt aber einige Doppelvorkommen, die du irgendwie aussortieren mußt). Alternativ kannst du die einzelnen Kombinationen in einer rekursiven Schleifenstruktur zusammenstellen.

Vielen Dank für deine Antwort

CStoll schrieb:

Du könntest per next_permutation() alle Permutationen von a..z durchlaufen lassen und dann jeweils die ersten n Elemente daraus rausgreifen (das erzeugt aber einige Doppelvorkommen, die du irgendwie aussortieren mußt).

So in etwa hatte ich mir das auch schon überlegt, aber dabei geht doch einiges an Performance verloren, oder?

CStoll schrieb:

Alternativ kannst du die einzelnen Kombinationen in einer rekursiven Schleifenstruktur zusammenstellen.

Hört sich interessant an, leider verstehe ich nicht ganz was du damit meinst.
Falls du Zeit/Lust hast kannst du mir ja vielleicht das Vorgehen etwas genauer beschreiben bzw. eine Beispiel posten.

CStoll

Ich meinte damit, daß du nacheinander für jede Position alle möglichen Werte durchprobieren solltest:

void get_comb(sbeg,send,tbeg,tpos,tend)
{
  if(tpos==tend)
  {
    // verarbeite [tbeg,tend[;
    return;
  }
  for(spos=sbeg;spos!=send;++spos)
    if(find(tbeg,tpos,*spos)==tpos)
    {
      *tpos=*spos;
      get_comb(sbeg,send,tbeg,tpos+1,tend);
    }
}

(ohne Garantie)