Coding-Contest - die wenigsten Zeilen gewinnen

[feuervogel]

Hallo!

Da ich immer noch versuche, Sudokus zu lösen und gerade dabei bin, sie zu erstellen (weil ich dann die Lösung einfach ablesen kann), bin ich auf ein Problem gestoßen, dass mich schon öfters gestört hat.

Ich habe meinetwegen die Zahlen 1 bis 5 und hätte diese gerne in allen möglichen Kombinationen, also 1 2 3 4 5, 1 3 2 4 5, 1 4 2 3 5 usw.

Wenn es bis 2 gehen soll sieht das komplett so aus:

1 2
2 1

Wenn es bis 3 gehen soll, so:

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

So. Ich war bis eben auf der Suche nach einem Algorithmus, der es mir für n = 9 erstellt. Ich war zu verknotet im Gehirn um einen schönes Programm zu schreiben, dass mir da ganze nacheinander aufbaut, und vorhin auf der Couch ist mir dann die Idee gekommen für etwas, das sich sehr schnell programmieren lässt, sehr kurz ist, aber relativ lange braucht.

Folgende Regeln: Man schreibe eine Funktion, wenn man in dieser auf andere selbstgeschriebene Funkionen zurückgreift, müssen diese mitgezählt werden.

Zurückgegeben wird für Argument $n ein Array mit $n ! (Fakultät) Elementen, die Schlüssel schön aufsteigend von 0 beginnend. Die Elemente sind wiederum Arrays mit den Zahlen, für $n = 2 sollte die Rückgabe also ein Array sein dass wie folgt aufgebaut ist:

array( array( 1 , 2 ) , array( 2 , 1 ) )

mal gucken, wer meine 18 zeilen unterbieten kann...

[langwebdesign]

Hi feuervogel,

ich hab noch nicht viel mit Algorithmen gemacht.
Kannst du mir villeicht deinen per pm schicken - oder hier posten - würde mir den gern mal anchauen.

mfg stephan

[Opendix]

also ich hab eins mit 17 zeilen... aber das geht nur gut solange es nicht zuviele Zahlen hat...also bei 9 Zahlen biste schon ein ganzes weilchen dran... wen er überhaupt mal fertig wird *g*

also neben dieser wirklich blöden Lösung hab ich bis jetzt noch nichts besseres gefunden :(

[feuervogel]

Zitat von langwebdesign

Hi feuervogel,

ich hab noch nicht viel mit Algorithmen gemacht.
Kannst du mir villeicht deinen per pm schicken - oder hier posten - würde mir den gern mal anchauen.

mfg stephan

ich werde meine funktion mal anhängen, wer lust hat kann ja gucken...narf, php-dateien kann man nicht anhängen...na gut, dann eben so:

da: http://nopaste.php-q.net/220704

achja, bei n = 7 brauche ich unter einer sekunde, bei n = 8 6 sekunden und bei n = 9 so gut 1.5 minuten...

[feuervogel]

mir fiel grade ein: ich könnte auch noch ne zeile weglassen, aber dann dauerts bei n = 9 wieder ne minute länger...das ist mir zu doof *g*

[MatMel]

PHP-Code:

function zahlen($n) {
for($i=$n;$i>0;$i--){ 
   $fak = $fak * $i;
}
for($u = 1; $u<=$fak; $u++){
   $gotone = false;
   while(!$gotone){
      for($w=1;$w<=$n;$w++){
         $zufz = rand(1,$n);
         if(!in_array($zufz, $zuf)){$zuf[$w] = $zufz;
         }
      }
   if(!in_array($zuf, $zahlen){
      $zahlen[$u] = $zuf; $gotone=true;
   }
}
return $zahlen;
} 


Mein sehr toller Versuch mit der Brecheisenmethode ;)
Also es könnte gehn und hat nich so arg viele Zeilen ...

Gruß,
Matze

[feuervogel]

PHP-Code:

function zahlen($n) {
for($i=$n;$i>0;$i--){ 
   $fak = $fak * $i;
} 


alleine daran habe ich so meine zweifel...$fak ist ja nicht belegt. man müsste vor die for-schleife noch ein $fak = 1; setzen.

[Morrandir]

Tja Leute ich weiß nicht wie du Zeilen Zählst, wenn du einzelne geschweifte Klammern mitzählst sind es 16 Zeilen wenn du sie nicht mitzählst (was ich nach einem Blick auf dein Code mal gerechnet habe) sind es 13...

Kleine Info nebenbei... bei 9 Zahlen = 362880 Möglichkeiten dauer = 2 Sekunden *g*...

Hier meine Funktion:

PHP-Code:

function combo($n){
    $fak = 1;
    for($i=1;$i<=$n;$i++){
        $array[]=$i;
        $fak = $fak * $i;
    }
    while($z < $fak)
        for($walk=0;$walk < sizeof($array)-1;$walk++){
            $ret[] = $array;
            $buffer = $array[$walk];
            $array[$walk] = $array[$walk+1];
            $array[$walk+1] = $buffer;
            $z++;
        }
    return $ret;
} 


Systemdaten stehen in der Signatur...

MfG
Morrandir

P.S.: Copyright by Morrandir 2006!!! Einstweilige Optimierungen an diesem Code bleiben mir alleine vorbehalten *g*...

[Serp]

So, ich denk, ich hab was ganz nettes gefunden... Allerdings muss ich zugeben, dass so was in der Art schon mal in ner Übungsaufgabe dran war, musste mich also nur noch erinnern... ;)

Länge kommt darauf an, was man alles als eine Zeile zählt. Ich würd vorschlagen, pro Anweisung (also pro ;) eine Zeile zu zählen. Zusätzlich noch jeweils eine Zeile pro Funktionsdefinition. Feuervogels Lösung käme damit auf 11 Zeilen, meine auf 8. Falls es ähnlich wie Feuervogels Script formatiert und dann gezählt werden soll, käme ich auf 13 Zeilen.

Laufzeit kann sich denk ich auch sehen lassen, auf meinem Rechner brauch ich für n = 7 etwa ne Zehntelsekunde, für n = 8 eine und für n = 9 etwa 12 Sekunden. Is denk ich ganz ordentlich. :)

Zugrundeliegender Code, auf Platzersparnis formatiert:

PHP-Code:

  function insertIntoPerm($value, $list) {
    foreach(perms($list) as $perm) 
      for($i = 0; $i <= count($perm); $i++) 
        $newPerm[] = array_merge(array_slice($perm, 0, $i), array($value), array_slice($perm, $i, count($perm)));
    sort($newPerm);
    return $newPerm;
  }

  function perms($arr) {
    if(!is_array($arr)) $arr = range(1, $arr);
    if(count($arr) <= 1) return array($arr);
    return insertIntoPerm(array_pop($arr), $arr);
  } 


[Morrandir]

Hilf mir mal mit deiner Zählung... da hab ich dann 9, oder?