Hallo,

wenn ich folgende Aufgabe habe: "Given the three letters "CAT" list all possible permutations."

Dann heißt es doch erstmal, weil es 3 Buchstaben sind, dass es 3! (Fakultät) = 6 ist. Also 6 Ergebnisse.

Die dürften dann aber nicht doppelt vorkommen, oder?

Das wäre doch dann CAT, CTA, ACT, ATC, TCA, TAC ... oder?

Ich habe nämlich eine Mitschrift von jemanden, der CAT, CTA, ACT, ATC, CTA, CAT hat... aber da kommt ja einiges doppelt vor. Oder ist es nicht erlaubt, dass da T am Anfang steht oder was gibt's da für Regeln?

Hallo,

Du hast es schon richtig verstanden.
Alle Permutationen bedeutet, alle Möglichkeiten ein mal. Keine Doppelten und das T darf natürlich am Anfang stehen.

Gruß

Edit: "Hallo" und "Gruß" eingefügt

Dankeschön.

Jetzt habe ich eine zusätzliche Aufgabe, dazu und die Mitschrift im Anhang als Lösung. Nur kann ich das alles nicht ganz nachvollziehen. Was genau wurde da gemacht? Und wieso steht da manches leer, also in 2 Anführungszeichen?

Wie schon drüber steht wurden ganz einfach alles subsets ermittelt. Man könnte auch sagen das das Power set ermittelt wurde da dies ja ein set aus allen subsets ist.

Hier das Beispiel von Wikipedia:

Code :

1 2 3 4 5 6 7 8 9 10

If S is the set {x, y, z}, then the subsets of S are:       * {} (also denoted \emptyset, the empty set)     * {x}     * {y}     * {z}     * {x, y}     * {x, z}     * {y, z}     * {x, y, z}

Und hier noch eins:

Code :

1 2 3 4 5 6 7 8 9 10 11

Array = [Hund, Katze, Maus]   Alle mögl. subsets [,,] [,,Maus] [,Katze,] [,Katze,Maus] [Hund,,] [Hund,,Maus] [Hund,Katze,] [Hund,Katze,Maus]

Hallo,

schau mal hier:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

package de.tutorials.training;   import java.util.ArrayList; import java.util.Arrays; import java.util.List;     public class PermutationExample {     public static void main(String[] args) {      Object[] o = {'C','A','T'};               for(Object[] permutation : new Permutations().computePermutations(o)){         System.out.println(Arrays.toString(permutation));       }     }       static class Permutations{             List<Object[]> permutations;             public List<Object[]> computePermutations(Object[] values){        this.permutations = new ArrayList<Object[]>();        permut(values,values.length-1);        return permutations;       }             void permut(Object[] values, int endIndex) {         if (endIndex==0){           this.permutations.add(values.clone());         }else{           permut(values, endIndex-1);           for (int i=0; i<=endIndex-1; i++){             swap(values, i, endIndex);             permut(values, endIndex-1);             swap(values, i, endIndex);           }         }       }             static void swap(Object[] values, int i, int j) {         Object temp = values[i];         values[i] = values[j];         values[j] = temp;       }     } }

Ausgabe:

Code :

1 2 3 4 5 6

[C, A, T] [A, C, T] [T, A, C] [A, T, C] [C, T, A] [T, C, A]

Gruß Tom

@Thomas

Das sind jetzt aber wieder alle möglichen Permutationen und nicht subsets.
Ich erwähne das nur damit sie jetzt nicht durcheinander kommt.

Danke dir rd4eva, das leuchtet mir ein. Jedoch unterscheidet sich das doch von der Mitschrift... was mich momentan noch verwirrt...

Auch wenn ich bei der Mitschrift auch nicht ganz durchblicke sieht zumindest alles was rechts unten steht wie die einzelnen subsets aus.

Subsets von CAT =>
[C,A,T]
[C,A,""]
[C,"",T]
["",A,T]
[C,"",""]
["",A,""]
["","",T]
["","",""]

Okay, danke dir.

Vielleicht habe ich eins vergessen zu erwähnen warum mich das so verwirrte. Also, erstmal weil ich in der Vorlesung nicht dabei war und die Lösung vom Dozenten selbst von der Tafel abgeschrieben wurde.
Und zweitens ist dies die exakte Aufgabenstelluing dazu:

Write pseudo-code that will list all possible subsets of a give string.

Dann setze ich wohl immer nur eine pseudo-Methode wie z.B.

Code :

1	recursiveSub("C","A","T");

davor, oder?

Hallo,

@Thomas

Das sind jetzt aber wieder alle möglichen Permutationen und nicht subsets.
Ich erwähne das nur damit sie jetzt nicht durcheinander kommt.

Huch, das hab ich leider nicht gesehen...

Schau mal hier:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

package de.tutorials;   import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; import java.util.Set;   public class SubSets {       public static void main(String[] args) {         Set<String> set = new HashSet<String>();         set.add("C");         set.add("A");         set.add("T");           Set<Set<String>> powerSet = powerSet(set);         System.out.println(powerSet);     }       private static <T> Set<Set<T>> powerSet(Set<T> set) {         Set<Set<T>> powerSet = new LinkedHashSet<Set<T>>();         List<T> items = new ArrayList<T>(set);                 int numberOfItems = items.size();         int numberOfSets = (int) Math.pow(2, set.size());                 for (int i = 0; i < numberOfSets; i++) {             Set<T> subSet = new HashSet<T>();             for (int j = 0; j < numberOfItems; j++) {                 boolean bitIsSet = ((i >> j) & 1) == 1;                 if (bitIsSet) {                     T item = items.get(j);                     subSet.add(item);                 }             }             powerSet.add(subSet);         }                 return powerSet;     } }

Ausgabe:

Code :

1	[[], [T], [A], [T, A], [C], [T, C], [A, C], [T, A, C]]

Gruß Tom

Danke dir Tom, aber mir geht es gerade ehrlich gesagt nicht um den Java-Code, sondern um die Mitschrift, die mir gerade am Herzen liegt, auch wenn ich deine Mühe echt zu schätzen weiß!

Ich verstehe gerade nicht so ganz warum du dich so an der Mitschrift aufhängst. Ziel sollte es doch sein das Problem bzw. die Lösung zu verstehen und nicht das gekrakel eines Kollegen.

Ich hab das ganze mal schnell in C# gebastelt.

Code csharp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

using System; using System.Collections.Generic; using System.Linq;   namespace PowerSet {     class Program     {                 static void Main(string[] args)         {             string given = "CAT";             char[] givenAsCharArr = given.ToCharArray();             getSubsets(givenAsCharArr, givenAsCharArr.Length, 0, new List<string>());                         Console.ReadKey();         }           static void getSubsets(char[] arr, int size, int index, List<string>subset)         {             if (index == size)             {                 Console.WriteLine(string.Join(",", subset));                 return;             }                         getSubsets(arr, size, index + 1, subset);                         subset = (subset.Take(subset.Count)).ToList();             subset.Add(arr[index].ToString());             getSubsets(arr, size, index + 1, subset);                   }             } }

Du kannst ja mal versuchen aus Thomas' oder meinem Code einen PseudoCode zusammen zu kritzeln.