Das finden der Teilmengen von einem array in PHP

Ich habe ein Relationales Schema mit den Parametern (A, B, C, D).
Ich habe eine Menge von Funktionalen Abhängigkeiten das bei mir auch.

Nun muss ich feststellen, das die Schließung für alle möglichen Teilmengen von R auf die Attribute. Das ist, wo ich geblieben bin. Ich muss lernen, Sie zu finden Teilmengen (nicht wiederholte) in PHP.

Mein Array ist wie folgt gespeichert.

$ATTRIBUTES = ('A', 'B', 'C', 'D').

also mein Teilmengen werden sollte

$SUBSET = ('A', 'B', 'C', 'D', 'AB', 'AC', AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'BCD', 'ABCD')

Den code sollte nicht etwas großes, aber für einige Grund, warum ich nicht bekommen kann meinen Kopf um ihn herum.

Bestellen egal? Auch ich denke, dass Sie möglicherweise verwenden Sie Rekursion.
Nein, die Reihenfolge nicht egal. ich kann, um es durch die Größe der string später, ich muss nur ein Weg, um die Teilmengen
Im Grunde sind Sie nur auf der Suche nach der handshake-Algorithmus?
das ist mehr ein power set Frage. Sie Fragen, um die Leistung zu erzeugen'set von $attributes
php.net/manual/en/function.shuffle.php#88408 ist ein power-set-generator Beispiel in php
genau, die Menge aller Teilmengen oder die powerset. all dieser Zeit ich war auf der Suche mit dem falschen Stichwort. danke. edit: wenn u wollen, u kann machen, dass eine Antwort,ich kann wählen u bis. Frieden

InformationsquelleAutor dtx | 2011-05-23

23

Wünschen Sie für die Potenzmenge $attributes? Das ist das, was Ihre Frage impliziert.

Kann ein Beispiel gefunden hier (zitiert auf Vollständigkeit)
```
<?php 
/** 
* Returns the power set of a one dimensional array, a 2-D array. 
* [a,b,c] -> [ [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c] ]
*/ 
function powerSet($in,$minLength = 1) { 
   $count = count($in); 
   $members = pow(2,$count); 
   $return = array(); 
   for ($i = 0; $i < $members; $i++) { 
      $b = sprintf("%0".$count."b",$i); 
      $out = array(); 
      for ($j = 0; $j < $count; $j++) { 
         if ($b{$j} == '1') $out[] = $in[$j]; 
      } 
      if (count($out) >= $minLength) { 
         $return[] = $out; 
      } 
   } 
   return $return; 
} 
```
- geil war das Sie versuchen zu konvertieren, das von der java one, die nicht arbeiten das ist 🙂
- gibt es eine Möglichkeit, dies zu ändern, so WIRD es wieder wiederholt? ie von (1,2,3) return (2 3)(1 2)(1 3)(1 2 3)(1 1 2)(1 1 3)(2 2 1) etc?
- Technisch ist diese Ausgänge alle Teilmengen bar die leere Menge. Nur ein technischer Punkt - ist es nicht genau der Satz macht in einem array.
- Das ist leicht zu beheben, ändern Sie $return = array(); zu $return = array(array());
- Entfernen $b=sprintf(...) verwenden $i>>$j&1 statt $b{$j} == '1' - kürzer und schneller.
- Zum Rendern $membersund $count veraltet: for($i=1<<count($in);--$i;){$out=[];foreach($in as$j=>$u)if($i‌>>$j&1)$out[]=$u];...}. Auf diese Weise (mit $i nicht schlagen 0), es ist auch garantiert, dass $out ist nie leer, so dass, wenn $minLength ist 1 ist, brauchen Sie nicht count($out) entweder.
InformationsquelleAutor fbstj

Mit php array_merge können wir eine schöne kurze powerSet Funktion

function powerSet($array) {
    //add the empty set
    $results = array(array());

    foreach ($array as $element) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($element), $combination);
        }
    }

    return $results;
}

Schlicht und einfach, das sollte die richtige Antwort, nicht der Müll oben geschrieben mit allen Respekt.

InformationsquelleAutor Yada

Hier eine backtracking-Lösung.

gegeben sei eine Funktion zurückgibt, die alle L-Länge Teilmengen der input-set, finden Sie alle L-Länge Teilmengen von L = 2 auf Datensatz-Eingabe Länge

<?php

function subsets($S,$L) {
    $a = $b = 0;
    $subset = [];
    $result = [];
    while ($a < count($S)) {
        $current = $S[$a++];
        $subset[] = $current;
        if (count($subset) == $L) {
            $result[] = json_encode($subset);
            array_pop($subset);
        }
        if ($a == count($S)) {
            $a = ++$b;
            $subset = [];
        }
    }
    return $result;
}



$S = [ 'A', 'B', 'C', 'D'];
$L = 2;


//L = 1 -> no need to do anything
print_r($S);

for ($i = 2; $i <= count($S); $i++)
    print_r(subsets($S,$i));

InformationsquelleAutor disf.asia

Basierend auf @Yada ' s Antwort, dies erzeugt die Potenzmenge ein array, aber die Erhaltung der ursprünglichen array-keys in jeder Teilmenge (der return-Wert ist immer noch numerisch & sequentiell, indiziert). Dieser sehr nützlich, wenn Sie Teilmengen eines assoziativen Arrays.

Den Teilmengen auch weiterhin das element, um das ursprüngliche array. Ich fügte hinzu, eine stabile Sorte zu $results weil ich es brauchte, aber Sie können es weglassen.

function power_set($array) {
    $results = [[]];
    foreach ($array as $key => $value) {
        foreach ($results as $combination) {
            $results[] = $combination + [$key => $value];
        }
    }

    # array_shift($results); # uncomment if you don't want the empty set in your results
    $order = array_map('count', $results);
    uksort($results, function($key_a, $key_b) use ($order) {
        $comp = $order[$key_a] - $order[$key_b]; # change only this to $order[$key_b] - $order[$key_a] for descending size
        if ($comp == 0) {
            $comp = $key_a - $key_b;
        }
        return $comp;
    });
    return array_values($results);
}

Bestimmten OP ' s input var_dump(power_set(['A', 'B', 'C', 'D'])); bietet:

array(16) {
  [0] =>
  array(0) {
  }
  [1] =>
  array(1) {
    [0] =>
    string(1) "A"
  }
  [2] =>
  array(1) {
    [1] =>
    string(1) "B"
  }
  [3] =>
  array(1) {
    [2] =>
    string(1) "C"
  }
  [4] =>
  array(1) {
    [3] =>
    string(1) "D"
  }
  [5] =>
  array(2) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
  }
  [6] =>
  array(2) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
  }
  [7] =>
  array(2) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [8] =>
  array(2) {
    [0] =>
    string(1) "A"
    [3] =>
    string(1) "D"
  }
  [9] =>
  array(2) {
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [10] =>
  array(2) {
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [11] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [12] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [13] =>
  array(3) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [14] =>
  array(3) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [15] =>
  array(4) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
}

InformationsquelleAutor Walf

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.