ARRAY: alle möglichen Kombinationen

Tentacle · 11.05.2006, 17:38

Hi Leute,

falls der Thread hier eher ins Anfängerforum gehört, verschiebt ihn, aber ich mach mir seit ner Stunde Gedanken um folgendes Problem und ich würd mich eher nicht als "Anfänger" bezeichnen. Vielleicht hab ich auch nur nen Blackout. Jedenfalls hier mein Problem und ich hoffe, ihr könnt mir weiterhelfen:

- Ich habe ein Array mit einer variablen Anzahl an Einträgen (zwischen 0 und ca. 10).
- Ich brauche daraus ein mehrdimensionales Array, das mir alle möglichen Kombinationen dieser Array-Elemente auflistet

Als Beispiel:

gegebenes Array:

Code:

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
)

gefordetetes Array:

Code:

Array
(
    [0] => Array
        (
        )

    [1] => Array
        (
            [0] => 1
        )

    [2] => Array
        (
            [0] => 2
        )

    [3] => Array
        (
            [0] => 3
        )

    [4] => Array
        (
            [0] => 1
            [1] => 2
        )

    [5] => Array
        (
            [0] => 1
            [1] => 3
        )

    [6] => Array
        (
            [0] => 2
            [1] => 3
        )

    [7] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
        )

)

Weiß jemand Rat?

Flor1an · 11.05.2006, 18:06

Naja das geht schon mit mehreren Schleifen und so. Musst halt nen Array erstellen mit allen und mit keinem Inhalt. Und dann hier nen Bsp: k=5 (Anzahl der Inhalte also 1-5)

Erst für k=1, da gibts die Lösungen 1,2,3,4,5
dann für k=2 dann musste ne Schleife undzwar:
erstes Element 1: durchgehen für alle anderen also 2,3,4,5 und kombinieren ...
zweites Element: durchgehen für alle außer dem ersten element 3,4,5
etc ...
dann k=3 bis eben k=anzahl-1=4 ...

Ist zwar umständlich aber so gehts

Waq · 11.05.2006, 18:14

Ein ähnliches Problem wurde hier behandelt:
http://forum.developers-guide.net/showthread.php?t=3503

Muss man natürlich umschreiben, da es nicht um die Summen geht und man alle Konstellationen haben will und nicht nur die, die eine gewisse Bedingung erfüllen, aber das sollte ein Fortgeschrittener eigentlich hinbekommen

Wobei die rekursive Variante ohne Schleifen eleganter ist...

PS: Der Fachbegriff für das Gesuchte lautet Potenzmenge
http://de.wikipedia.org/wiki/Potenzmenge

CC84 · 11.05.2006, 21:10

habe hier noch nen Script, das deine Wünsche erfüllen sollte:

PHP-Code:

  function potenzmenge($array){

    $results = array(array());

    

    foreach ($array as $element)

        foreach ($results as $combination)

            array_push($results,array_merge(array($element),$combination));

    return $results;

}

Zergling-new · 11.05.2006, 23:08

ich finde ein Fortgeschrittener darf ruhig auch selbst eigene Überlegungen anstellen und präsentieren, eine Frage in den Raum stellen ist einfach zu wenig...

Deshalb, Thread verschoben:
Fortgeschrittene

Anfänger

(das übernehme ich auch gleich mal in die Boardregeln)

KingCrunch · 11.05.2006, 23:28

naja, er hat gesagt, dass er daran schon seit einiger zeit arbeitet

Zergling-new · 11.05.2006, 23:34

behaupten alle, irgendwas muss ja bei rumgekommen sein und das kann man ja mal zeigen

aber ist ja auch egal

Letztlich ist das ganze mit Rekursion wahrscheinlich sogar mit relativ wenig Code zu lösen. Mal überlegen. Bis gleich

KingCrunch · 11.05.2006, 23:53

Denke, Iteration reicht, is auch perfomanter...

PHP-Code:

  $in = array(1,2,3);

$out = array(array());

foreach ($in as $val1) {

    $temp = $out;

  foreach ($out as $key2 => $val2) {

    $out[$key2][] = $val1;

  }

  $out = array_merge($temp,$out);

}

beinhaltet allerdings auch nen leeres Array, was aber so weit meine Erinnerung des letzten Semester noch aufkeimen, durchaus auch zur Potenzmenge gehört. Ansonsten kann man die sicher auch catchen

KingCrunch · 11.05.2006, 23:57

PHP-Code:

  $in = array(1,2,3);

$out = array(array());

foreach ($in as $val1) {

    $temp = $out;

  foreach ($temp as $val2) {

    $out[] = array_merge($val2,array($val1));

  }

}

Noch ne schönere variante

Zergling-new · 12.05.2006, 00:02

PHP-Code:

 
START
 
<?php

error_reporting(E_ALL);

$total = array();

$c = 0;

function JederMitJedem($list, $depth = 0)

{

    global $total, $c;

    

    if ($c++ > 100)

        return;

    

    $total[] = array($list);

    foreach ($list as $key => $value) {

        $newlist = $list;

        unset($newlist[$key]);

        JederMitJedem($newlist, ++$depth);

    }

}

$list = array(1,2,3,4);

JederMitJedem($list);

print "<hr />";

echo '<pre>', print_r($total, true), '</pre>';

?>

ENDE

Nicht schön (aber so darf das beim Entwickeln ruhig mal sein) und der
komische Ergebnis-Array wundert mich auch (warum hat der eine
überflüßige Dimension), deshalb geht array_unique() nicht...Ich kümmer
mich morgen nochmal drum.

Bin aber auch bissl neben der Kapp grad, bis ich gemerkt hab, dass ich
keine for-Schleife benutzen darf :Z

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Turnierbaum aus array erstellen	kingflo	PHP-Fortgeschrittene	11	30.07.2008 11:32
Soapfault: Undefined Property	Argi	PHP-Fortgeschrittene	0	28.07.2008 11:17
Kategoriedaten rekursiv in Array bringen	Schiedsrichter	PHP Tipps 2008	2	10.12.2007 15:43
Übersicht aus mehrdimensionalem Array erzeugen	Crypi	PHP-Fortgeschrittene	0	30.01.2006 13:44
Array auslesen	andrew22	PHP Tipps 2006	3	21.01.2006 23:06
Array Formatierung		PHP Tipps 2006	3	17.01.2006 19:12
Menü mit Unterpunkten	supertramp	Beitragsarchiv	7	18.10.2005 22:40
Problem beim vergleichen von 2 Arrays		PHP Tipps 2005-2	1	06.10.2005 14:25
(schnellere) Funktion zum Zusammenfassen von CSS		PHP-Fortgeschrittene	21	08.08.2005 16:47
Sortieren von Arrays mit mehr als 2 Dimensionen (Teil 2)	Buhmann	PHP-Fortgeschrittene	4	12.07.2005 14:03
Array wie auslesen?		PHP Tipps 2005	7	07.03.2005 11:43
Mehrdimensionales Array in eindimensionales Array umwandeln		PHP-Fortgeschrittene	3	03.01.2005 22:31
Abfrage mit id aus anderer Tabelle	suter	PHP Tipps 2004-2	15	16.12.2004 14:25
Was ist hier mit Schleife und mehrdimensionalen Array falsch		PHP Tipps 2004	8	25.10.2004 14:02

11.05.2006, 17:38
Tentacle Neuer Benutzer Registriert seit: 06.10.2005 Beiträge: 25	ARRAY: alle möglichen Kombinationen Hi Leute, falls der Thread hier eher ins Anfängerforum gehört, verschiebt ihn, aber ich mach mir seit ner Stunde Gedanken um folgendes Problem und ich würd mich eher nicht als "Anfänger" bezeichnen. Vielleicht hab ich auch nur nen Blackout. Jedenfalls hier mein Problem und ich hoffe, ihr könnt mir weiterhelfen: - Ich habe ein Array mit einer variablen Anzahl an Einträgen (zwischen 0 und ca. 10). - Ich brauche daraus ein mehrdimensionales Array, das mir alle möglichen Kombinationen dieser Array-Elemente auflistet Als Beispiel: gegebenes Array: Code: Array ( [0] => 1 [1] => 2 [2] => 3 ) gefordetetes Array: Code: Array ( [0] => Array ( ) [1] => Array ( [0] => 1 ) [2] => Array ( [0] => 2 ) [3] => Array ( [0] => 3 ) [4] => Array ( [0] => 1 [1] => 2 ) [5] => Array ( [0] => 1 [1] => 3 ) [6] => Array ( [0] => 2 [1] => 3 ) [7] => Array ( [0] => 1 [1] => 2 [2] => 3 ) ) Weiß jemand Rat?


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

11.05.2006, 18:06
Flor1an ¯\_(ツ)_/¯ Registriert seit: 18.06.2008 Beiträge: 8.814 PHP-Kenntnisse: Fortgeschritten	Naja das geht schon mit mehreren Schleifen und so. Musst halt nen Array erstellen mit allen und mit keinem Inhalt. Und dann hier nen Bsp: k=5 (Anzahl der Inhalte also 1-5) Erst für k=1, da gibts die Lösungen 1,2,3,4,5 dann für k=2 dann musste ne Schleife undzwar: erstes Element 1: durchgehen für alle anderen also 2,3,4,5 und kombinieren ... zweites Element: durchgehen für alle außer dem ersten element 3,4,5 etc ... dann k=3 bis eben k=anzahl-1=4 ... Ist zwar umständlich aber so gehts __________________ ▇█▓▒░◕‿‿◕░▒▓█▇

11.05.2006, 18:14
Waq Erfahrener Benutzer Registriert seit: 15.08.2004 Beiträge: 2.473	Ein ähnliches Problem wurde hier behandelt: http://forum.developers-guide.net/showthread.php?t=3503 Muss man natürlich umschreiben, da es nicht um die Summen geht und man alle Konstellationen haben will und nicht nur die, die eine gewisse Bedingung erfüllen, aber das sollte ein Fortgeschrittener eigentlich hinbekommen Wobei die rekursive Variante ohne Schleifen eleganter ist... PS: Der Fachbegriff für das Gesuchte lautet Potenzmenge http://de.wikipedia.org/wiki/Potenzmenge __________________ mod = master of disaster

11.05.2006, 21:10
CC84 Erfahrener Benutzer Registriert seit: 03.01.2006 Beiträge: 253	habe hier noch nen Script, das deine Wünsche erfüllen sollte: PHP-Code: `function potenzmenge($array){ $results = array(array()); foreach ($array as $element) foreach ($results as $combination) array_push($results,array_merge(array($element),$combination)); return $results; }`

11.05.2006, 23:08
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	ich finde ein Fortgeschrittener darf ruhig auch selbst eigene Überlegungen anstellen und präsentieren, eine Frage in den Raum stellen ist einfach zu wenig... Deshalb, Thread verschoben: Fortgeschrittene Anfänger (das übernehme ich auch gleich mal in die Boardregeln)

11.05.2006, 23:28
KingCrunch Erfahrener Benutzer Registriert seit: 13.08.2007 Beiträge: 1.976	naja, er hat gesagt, dass er daran schon seit einiger zeit arbeitet __________________ Nicht jeder Fehler ist ein Bug.

11.05.2006, 23:34
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	behaupten alle, irgendwas muss ja bei rumgekommen sein und das kann man ja mal zeigen aber ist ja auch egal Letztlich ist das ganze mit Rekursion wahrscheinlich sogar mit relativ wenig Code zu lösen. Mal überlegen. Bis gleich

11.05.2006, 23:53
KingCrunch Erfahrener Benutzer Registriert seit: 13.08.2007 Beiträge: 1.976	Denke, Iteration reicht, is auch perfomanter... PHP-Code: `$in = array(1,2,3); $out = array(array()); foreach ($in as $val1) { $temp = $out; foreach ($out as $key2 => $val2) { $out[$key2][] = $val1; } $out = array_merge($temp,$out); }` beinhaltet allerdings auch nen leeres Array, was aber so weit meine Erinnerung des letzten Semester noch aufkeimen, durchaus auch zur Potenzmenge gehört. Ansonsten kann man die sicher auch catchen __________________ Nicht jeder Fehler ist ein Bug.

11.05.2006, 23:57
KingCrunch Erfahrener Benutzer Registriert seit: 13.08.2007 Beiträge: 1.976	PHP-Code: `$in = array(1,2,3); $out = array(array()); foreach ($in as $val1) { $temp = $out; foreach ($temp as $val2) { $out[] = array_merge($val2,array($val1)); } }` Noch ne schönere variante __________________ Nicht jeder Fehler ist ein Bug.

12.05.2006, 00:02
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	PHP-Code: START <?php error_reporting(E_ALL); $total = array(); $c = 0; function JederMitJedem($list, $depth = 0) { global $total, $c; if ($c++ > 100) return; $total[] = array($list); foreach ($list as $key => $value) { $newlist = $list; unset($newlist[$key]); JederMitJedem($newlist, ++$depth); } } $list = array(1,2,3,4); JederMitJedem($list); print "<hr />"; echo '<pre>', print_r($total, true), '</pre>'; ?> ENDE Nicht schön (aber so darf das beim Entwickeln ruhig mal sein) und der komische Ergebnis-Array wundert mich auch (warum hat der eine überflüßige Dimension), deshalb geht array_unique() nicht...Ich kümmer mich morgen nochmal drum. Bin aber auch bissl neben der Kapp grad, bis ich gemerkt hab, dass ich keine for-Schleife benutzen darf :Z