Algorithmus zum erstellen aller Möglichen Kombinationen

[CloudStrife]

Hallo,

ich habe folgendes Probem zu lösen:

ich habe 11 variablen, die 16 verschieden Werte annehmen können (0-15).
es darf jedoch in einem Iterationsschritt kein Wert doppelt auftreten.

hat vielleicht jemand eine Idee wie ich alle möglichen Kombinationen generieren kann?
Vielen Dank schon mal im Voraus!!!

Gruß
Cloud

[cloidnerux]

Du legst ein Array mit 11 Variablen an.
Dann weißt du jedem einen Zufallswert zu.
Bei jedem mal prüfst du aber alle Vorhergehenden Variablen ob sie die Variable schon enthalten und wenn ja weißt du einen neuen Wert zu und wiederholst das Überprüfen solange bis es ein wert ist, der vorher noch nicht aufgetreten ist.

[sonic]

Vielleicht könntest du dir auch next_permutation aus der stl ansehen...

[CloudStrife]

Danke erst mal für eure (schnellen) Antworten.

Du legst ein Array mit 11 Variablen an.
Dann weißt du jedem einen Zufallswert zu.
Bei jedem mal prüfst du aber alle Vorhergehenden Variablen ob sie die Variable schon enthalten und wenn ja weißt du einen neuen Wert zu und wiederholst das Überprüfen solange bis es ein wert ist, der vorher noch nicht aufgetreten ist.

Vielleicht könntest du sich noch etwas klarer ausdrücken?!
Was meinst du mit jedeM einen Zufallswert zuweisen jedeM Array oder jedeR Variablen?
Die Idee zu Überprüfen ob eine Kombination schon vorhanden ist scheint mir sehr rechenintensiv. Außerdem möchte ich ein Konzept was nicht auf zufallszahlen basiert! Wer sagt mir denn ob ich überhaupt alle Kombinationen in einer vertretbaren zeit erreiche?

Gruß
Cloud

[Xin]

Hallo,

ich habe folgendes Probem zu lösen:

ich habe 11 variablen, die 16 verschieden Werte annehmen können (0-15).
es darf jedoch in einem Iterationsschritt kein Wert doppelt auftreten.

Einfach durchzählen.

16 Werte sind ein Nible, also 4 Bit.
11 Variablen sind also 44 Bit.
Also brauchst Du zwei ints oder ein double und zählst einfach bis 1 << 44 hoch.

Wenn Du zwei ints nimmst, zählst Du das höherwertige bis es 1<<12 erreicht und das niederwertige int zählst Du komplett für jeden Versuch des höherwertigen ints durch.
Die zwei Ints repräsentieren Deine Variabeln. Du kannst die den Wert der Variablen dann aus den Ints rausziehen (mit Hilfe der Bitoperatoren).

Der Spaß heißt Brute Force. Es kann nicht schaden, wenn Du dafür einen guten Rechner zur Verfügung hast, denn zwei verschachtelte Schleifen, bei der die innere über INT_MAX rennt, das erfordert schon ein paar Stunden... Tage? Geduld.

[AnGaiNoR]

Ich persönlich würde die Variante von Xin empfehlen (die aber leider nicht vollständig ist), habe aber auch noch eine parat
Du kannst einfach 11 for-Schleifen ineinander verschachteln, die je von 0 bis 15 gehen.

Code: Alles auswählen

// Feld für Zählervariablen
char i[11];

// wird später gebraucht
bool gleich;
char j, k;

for ( i[0] = 0; i[0] <= 15; ++i[0])
for ( i[1] = 0; i[1] <= 15; ++i[1])
// ... noch mehr Schleifenköpfe
for ( i[10] = 0; i[10] <= 15; ++i[10])
{
    // teste ob alle Werte verschieden sind
    gleich = false;
    for ( j = 0; j < 11; ++j )
    {
        for ( k = 0; k < 11; ++k )
        {
            // abbrechen wenn gleiche Elemente
            if ( j == k ) continue;

            // wenn Werte gleich, dann Abbruch einleiten
            if ( i[j] == i[k] )
            {
                gleich = true;
                break;
            }
        }

        // wenn gleich gesetzt wurde, dann brauchen die restlichen Werte nicht geprüft zu werden
        if ( gleich ) break;
    }

    // wenn gleich gesetzt ist, dann brich ab (fahre mit dem nächsten fort)
    if ( gleich ) continue;
 
    // mache irgendwas
}

Die Variante ist natürlich ineffizient und sehr schlecht lesbar oder gar erweiterbar, und erst recht nicht dynamisch!
Aber sie ist ganz einfach zu verstehen, und es gibt keine Dopplungen.

[Xin]

Ich persönlich würde die Variante von Xin empfehlen (die aber leider nicht vollständig ist)

Wieso nicht vollständig?

[CloudStrife]

Nur dass ich dich richtig verstehe Xin,

wenn ich einfach von 1 auf 44 Bit hochzähle, dann habe ich ja jede menge doppelte Werte?

Villeicht habe ich mich auch nicht klar ausgedrückt bei meiner Problembeschreibung, deshalb jetzt mal ein Bsp.:

var1 = 0 var2 = 1 var3 = 2
var4 = 3 var5 = 4 var6 = 5
var7 = 6 var8 = 7 var9 = 8
var10 = 9 var11 = 10

-> das ist eine mögliche Kombination bei der kein Wert doppelt auftritt. wie gesagt die Variablen dürfen alle Werte von 0-15 annehmen solange nicht 2 Variablen den gleichen Wert haben.

Wenn ich jetzt eine 44Bit zahl nehmeund die hochzähle passiert meiner meinung nach folgendes

var1 = 0000 var2 = 0000 var3 = 0000
var4 = 0000 var5 = 0000 var6 = 0000
var7 = 0000 var8 = 0000 var9 = 0000
var10 = 0000 var11 = 0001

so und beim nächsten schritt wird var11 dann 0010 und die anderen sind immernoch 0. das ist nicht das was ich wollte. Es darf KEIN Wert doppelt auftreten.

[Xin]

Nur dass ich dich richtig verstehe Xin,

wenn ich einfach von 1 auf 44 Bit hochzähle, dann habe ich ja jede menge doppelte Werte?

Villeicht habe ich mich auch nicht klar ausgedrückt bei meiner Problembeschreibung, deshalb jetzt mal ein Bsp.:

var1 = 0 var2 = 1 var3 = 2
var4 = 3 var5 = 4 var6 = 5
var7 = 6 var8 = 7 var9 = 8
var10 = 9 var11 = 10

Ah... okay, da hast Du natürlich recht, da habe ich Dich Mistverstanden. ^^

Okay... dann hast Du ein Backtracking-Problem, das ich wie folgt lösen würde. Erstmal pack Deine Variablen in ein Array.

Code: Alles auswählen

int main( void )
{
  int variables[11];

  backTracking( variables, 0 );

  return 0;
}

Anschließend schreibst Du eine rekursive Funktion: (ich schreibe die jetzt mal einfach so... heißt ungetestet...)

Code: Alles auswählen

void doSomethingWithCombination( int * variables )
{
  printf( "Kombination: " );

  for( int i = 0; i < 11; i++ )
    printf( "%d; ", variables[i];

  printf( "\n" );
}

bool contains( int * variables, int position, int value )
{
  for( int i = 0; i < position; i++ )
    if( variables[i] == value ) 
      return false;

  return true;
}

void backTracking( int * variables, int position )
{
  for( int i = 0; i <= 15; i++ )
    if( !contains( variables, position, i )
    {
      /* Mögliche Kombination für position gefunden */
      variables[ position ] = i;

      if( position == 10 )
        doSomethingWithCombination( variables );  // alle Variablen gesetzt -> Testen
      else
        backTracking( variables, position + 1 );  // nächste Variable setzen
    }
}

So, das ist nur flott hingeklatscht, also gehe ich mal davon aus, dass das hier nichtmals kompiliert.

Was passiert: Er geht alle Möglichkeiten durch, gibt also der ersten Variable eine 1. Wenn er an Position 10 (also 11. Variable) ist, passiert die Action - ist er aber nicht, also ruft er sich Rekursiv für Position 1 (2. Variable) auf und guckt dann, was er der zweiten Variable für eine Zahl geben kann. Er probiert die 1 und stellt über contains() fest, dass die Zahl bereits im Array ist. Also geht er in der Schleife weiter: 2? Passt. So hangelt er sich runter.

Nachdem er die für die 2. Variable nun durchgetestet hat, steckt er immernoch in der Schleife. Also probiert er als nächstes die 3. Vorher gibt es weiterhin nur die 1 im Array. Die drei passt also... und so geht er wieder weiter runter für die 3, 4...9, 10, 11 Variable.
Wann immer er Index 10 gesetzt hat und ruft er die Funktion doSomething...() auf, so dass Du damit Deinen Test fahren kannst.

Das Paradebeispiel zum Backtracking hier ist das Damenproblem.

[nufan]

Willst du eine Wordlist schreiben oder was? ^^
Hab mir mal selbst so ein Programm geschrieben (keine Sorge, das Ergebnis wurde noch nie verwendet ), das das auch ohne Backtracking und die ganzen Überprüfungen schafft. Ein paar verschachtelte Schleifen tun's auch. Nur mal so als Anregung:

Code: Alles auswählen

void hexadecimal (short minlength, short maxlength, FILE *list)
{

  char *str;
  int j, i;

  str = (char *) malloc (sizeof (char) * maxlength);

  for (i = 0; i < maxlength; i++)
    str[i] = 0;
      
  for (j = maxlength - 1; j >= minlength; j--)
  {        
  
    printf ("%d\n", j);
      
    while (str[j] == 0) 
    {
      
      for (i = j - 1; i >= 0; i--)
        fprintf (list, "%X", str[i]);
          
      fputc ('\n', list);  
      str[0]++;
      i = 0;
      
      while (str[i] > 15) 
      {
        str[i] = 0;
        i++;
        str[i]++;
      }
      
    }
      
  }    
  
  free (str);  

}

maxlength muss um 1 größer sein als die gewünschte Länge. Hier werden alle Möglichkeiten für die Stringlängen zwischen minlength und maxlength -1 gebildet.
Hinweis: Dieser Code dient nur Bildungszwecken ^^