Permutation mit Wiederholungen

[artus1977]

Hallo zusammen

Ich habe folgendes Problem.
Ich möchte alle Möglichkeiten herausfinden wie ich die 0en und 1en in einem bestimmten Array anordnen kann. Klingt jetzt wohl noch komplizierter als ich es eigentlich meine.

Anhand eines Beispiels sollte es aber klar werden was ich suche:
Ich habe folgende Liste: [1,1,1,0,0]
Jetzt möchte ich davon sämtliche Möglichkeiten, wie ich die 0en und 1en anordnen kann:

[1,1,1,0,0]
[1,1,0,1,0]
[1,1,0,0,1]
[1,0,1,1,0]
[1,0,1,0,1]
[1,0,0,1,1]
[0,1,1,1,0]
[0,1,1,0,1]
[0,1,0,1,1]
[0,0,1,1,1]

Im Netz finde ich immer nur die gleichen Beispiele mit Permutationen ohne Wiederholungen und etwas andere Aufgabenstellung als wie bei mir.
Ich hoffe jemand weiss eine "einfache" Lösung für mich.

Vielen Dank im Voraus

 

[HoaX]

Dann zweig doch mal deine Idee und was du schon hast und wo du nicht weiter kommst. Deine Hausaufgaben wird dir bestimmt keiner hier machen.

 

[langhaar!]

Du könntest rekursiv mit Arraylänge als Abbruchkriterium alle Möglichkeiten für beliebige 0 und 1 Kombinationen erzeugen und die enstehenden Kombinationen auf Gültigkeit testen (Einsen oder Nullen zählen).

EDIT
Ich habe das Programm mal geschrieben. Es ist ein 5-Zeiler. Den Zähler für die Nullen (oder die Einser) kann man als Parameter der Rekursionsmethode mitgeben.

 

[Marco13]

Wenn's nicht effizient sein soll und die Anzahl der Elemente nicht zu groß ist...

    private static void doit()
    {
        int n = 5;
        int k = 3;
        for (int j=0; j<(1<<n); j++)
        {
            int size = countBits(j);
            if (size == k)
            {
                int element[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                    long b = 1 << i;
                    if ((j & b) != 0)
                    {
                        element[i] = 1;
                    }
                }
                System.out.println(Arrays.toString(element));
            }
        }
    }
    public static int countBits(int n)
    {
        int m = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
        return ((m + (m >> 3)) & 030707070707) % 63;
    }

 

[artus1977]

Hi Marco13

Vielen Dank für die Lösung... funktioniert bestens.

Wenn ich das richtig verstehe, nimmst du jede Zahl und schaust, mit wie vielen bit sie geschrieben werden kann.
Wenn Anzahl bit und k übereinstimmt, muss es eine Lösung sein.

Die Methode countBits(int n) verstehe ich aber in ihrer Funktion nicht wirklich .... Als return wird die Anzahl bit's ausgegeben um n darstellen zu können, soweit so Gut .... kannst du mir vielleicht noch erklären, was die 2 Zeilen Code genau machen? Vor allem die 033333333333 und co's verwirren mich.

Danke nochmals ....

 

[Marco13]

Das ist schwarze Magie :shock: Nee im ernst, da gibt's nichts zu verstehen, das ist einfach eine funktion, die so gewählt ist, dass sie dieses Ergebnis liefert. Mehr von der Sorte gibt's auf Bit Twiddling Hacks (genau diese Methode jetzt nicht, die hatte ich mal auf einer ähnlichen Seite gefunden). Man könnte das auch einfach mit einer for-Schleife machen, das wäre etwas übersichtlicher....

 

[langhaar!]

Zum VErgleich mal meine Lösung von heute morgen:

	public void kombination(String erg, int count) {
		
		if (erg.length() < 5) {
			kombination("0"+erg,count);
			kombination("1"+erg,++count);
		} else {
			if (count == 3)
				System.out.println(erg);
		}
	}

Aufzurufen mit kombination("",0).

 

[artus1977]

Langhaar ...

Ehmmmm geile Lösung ;-)
Funktioniert perfekt!

 

[Tobse]

Was wurschtelt ihr denn da rum? Ein array mit 0en und einsen ist doch quasi eine zahl (im binärformat). Angeommen du hast ein

boolean[5]

Dann hast du

  2 ^ 0 * 1 = 1
+ 2 ^ 1 * 1 = 2
+ 2 ^ 2 * 1 = 4
+ 2 ^ 3 * 1 = 8
+ 2 ^ 4 * 1 = 16
            = 32 Möglichkeiten

Und die kannst du ermitteln, indem du die Java API zum umwandeln von ints in binär-strings benutzt. Dann nurnoch ein

int moeglichkeiten=...; // s.o.
for (byte i=0;i<moeglichkeiten;i++) {
     System.out.println(... i ...);
}

 

[Marco13]

Genau das wird in meine Code auch gemacht Ich hatte erst geschaut, ob in http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html schon was passendes dabei wäre, daher stammte das mit dem countBits, from scratch würde es wohl etwas anders aussehen, aber vom Ablauf her wäre es genau so.

 

[artus1977]

Hallo zusammen

Also ich für meinen Teil bin Happy über die beiden Lösungsvarianten.
Ich werde jetzt wohl die Variante von Langhaar für meine Zwecke anpassen und hemmungslos benutzen ;-)

Danke nochmals