# Permutation mit Wiederholungen



## artus1977 (25. Okt 2011)

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 (25. Okt 2011)

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! (25. Okt 2011)

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 (25. Okt 2011)

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 (25. Okt 2011)

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 (25. Okt 2011)

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! (25. Okt 2011)

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 (25. Okt 2011)

Langhaar ...

Ehmmmm geile Lösung ;-) 
Funktioniert perfekt!


----------



## Tobse (25. Okt 2011)

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 (25. Okt 2011)

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 (26. Okt 2011)

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


----------

