Kombination af tal

Du kan gøre det binært ---
har du f.eks. fem elementer ( A B C D E ), så kan du også sige, at det er det samme som binært 11111 (=31) - derefter skriver du bare alle "kombinationer" ned til 1, så har du alle kombinationer - og på en måde der gør at der ikke både optræder en B D  og en D  B...

Jeg har lavet noget java-kode her- den er måske lidt forvirrende - men selve princippet går ud på at sige
1) jeg har n elementer
2) derfor har jeg (2^n)-2 muligheder (0 fratrukket)
3) jeg skal starte med mulighed (2^n)-1 (dette kalder vi idx)
4) jeg skal finde ud af hvor der er "tændte bits" (1-taller) i tallet idx
5) udskrive de elementer, som passer til de tændte bits
6) træk 1 fra idx
7) hvis jeg ikke er nået til tallet 0, så skal jeg gå til trin 4 igen...


Her er koden...
public static void printCombos( String[] elems ) {
  int starttal = (int)Math.pow(2, elems.length) -1;  //(starttal er 2^n -1)
  for(int idx = starttal; idx>0; --idx) {
   
    // Hold en Stringbuffer, vi kan samle kombinationen i
    StringBuffer res = new StringBuffer();       

    // Find de elementer, som passer de tændte bits
    for(int p=elems.length-1; p>=0; --p) {
      int bitPos = (int)Math.pow(2,p);
      if( (idx & bitPos) == bitPos )        // IF idx AND bitPos == sand -- så udskriv elementet
        res.append(elems[p]);
      else
        res.append(" ");                   
    }

    // Udskriv strengen
    System.out.println( res.toString() );
  }
}

public static void main(String[] args) {
  String[] data = {"A", "B", "C", "D", "E"};
  printCombos( data );
}


udskrift hos mig
EDCBA
EDCB
EDC A
EDC
ED BA
ED B
ED  A
ED
E CBA
E CB
E C A
E C
E  BA
E  B
E  A
E
DCBA
DCB
DC A
DC
D BA
D B
D  A
D
  CBA
  CB
  C A
  C
  BA
  B
    A

/Søren

Du kunne (i PHP):

  function try($t,$m,$s) {
    if ($t>$m) {
      if ($s!="") print "$s  <br>\n";
    } else {
      try($t+1,$m,$s." $t");
      try($t+1,$m,$s);
    }
  }

  try(1,3,"");

Du skal bare ændre 3-tallet hvis øvre grænse skal være noget andet.

erik - kan du lige forklare, hvordan det ovenstående virker  - jeg kan ikke helt se mig ud af det... :-/

bearhugx: Tak, kigger på det senere.

erikjacobsen: Tak, men jeg fik ikke nævnt, at tallene ikke nødvendigvis er fortløbende. Istedet for 1 2 3 kunne det have været 5 3 13.

Kombinationer i Java:

public class Comb {
    public static void process(int[] b) {
        for (int j = 0; j < b.length; j++) {
            System.out.print(" " + b[j]);
        }
        System.out.println();
    }
    public static void allcomb(int[] a, int len, int[] b, int ix, int start) {
        if (ix < b.length) {
            for (int i = start; i < a.length; i++) {
                b[ix] = a[i];
                allcomb(a, len, b, ix + 1, i + 1);
            }
        } else {
            process(b);
        }
    }
    public static void allcomb(int[] a, int len) {
        int[] b = new int[len];
        allcomb(a, len, b, 0, 0);

    }
    public static void allcomb(int[] a) {
        for (int len = 1; len <= a.length; len++) {
            allcomb(a, len);
        }
    }
    public static void main(String[] args) {
        int[] a = { 1, 3, 5 };
        allcomb(a);
    }
}

Jeg har ikke brugt nogle af jeres svar direkte, men tak for inspiration.

Hvis det ikke skal være fortløbende tal (og stadig må være PHP), gør du bare:

  function try($t,$m,$s,$a) {
    if ($t>=$m) {
      if ($s!="") print "$s  <br>\n";
    } else {
      try($t+1,$m,$s." $a[$t]",$a);
      try($t+1,$m,$s,$a);
    }
  }

  try(0,3,"",array(7,9,13));


(det kan evt simplificeres en anelse mere...)

erikjacobsen : Ihh hvor pænt. Tak.