Subsets bestimmen

[Guest]

Hallo,

ich will von einer Menge von Zahlen, sagen wir 1,2,3,4, alle Subsets (mit mindestens 2 Elementen) bestimmen (keine doppelten). Bisher mache ich es so, dass ich ein int Array mit den zahlen habe, und dann rekursiv einen Algorithmus aufrufe, der eines der Elemente entfernt. D.h. z.B.

1,2,3,4 => 2,3,4 => 3,4

Ich bekomme so auch alle Subsets, aber zum einen ist es noch relativ langsam, zum anderen bekomme ich auch doppelte durch verschiedene entfernungswege, z.B. durch

1,2,3,4 => 1,3,4 => 3,4

die ich dann umständlich mittels HashMap rausfiltere.

Hat jemand eine Idee wie man so schnell wie möglich alle solche Subsets mit mindestens zwei Elementen bestimmen kann??

Grüsse, Mike

 

[SlaterB]

for (i =0 bis Länge-2) {
  for (j =i+1 bis Länge-1) {
      neue Liste mit i,j
  }
}

da gibts keine Doppelten?

 

[Guest]

Danke, aber das liefert nur alle Subsets mit Größe zwei! Und ich brauche alle mit Größe MINDESTENS zwei. Und gerade diese größeren sind leider mein problem........

 

[SlaterB]

ach ne, du willst ja nicht nur Zweier-Sets

also ne Rekursion:
1. Schritt:
0. Element drin lassen, Rekursion der Restliste aufrufen

wenn damit alle Subset mit dem 0. Element drin bestimmt sind,
n. Schritt:
0. Element entfernen, Rekursion der Restliste aufrufen

das 'drin lassen' oder 'entfernen' sollte sich auf eine zweite Liste beziehen, hoffentlich eine LinkedList,
die am Ende jeder Rekursion kopiert wird,

alternativ setzt man Flags in einem langen boolean-Array und erstellt mit diesem am Ende der Rekursion eine neue Liste aus der Ursprungsliste,
kannst ja mal testen was schneller ist

 

[SlaterB]

oder du baust den Zweier-Finder zu einem n-Finder um,
bestimmst also erst alle Zweier, dann Dreier, ...,

man kann natürlich nicht dynamisch viele for-Schleifen bauen,
sondern hat dann ein index-Array,
dass für 5 z.B. mit 0,1,2,3,4 anfängt und dann nach bestimmten Regeln hochzählt,

0,1,2,3,4
0,1,2,3,5
0,1,2,3,6
..
0,1,2,3,79
0,1,2,4,5
0,1,2,4,6
....

 

[huckfinn]

Hi,

Ich habe das mal als "Rotierende Ketten" implementiert. Das ist wie die Stellen auf einer Registrierkasse nur das die "Digits" jetzt die Listenwerte haben. Zur Anschauung kopiere ich Daten in Puffer und rotiere dort. Das wird normalerweise nicht gemacht. Um es effizient zu gestalten wird nur der Adresspoiter des "Digits" rotiert das ist viel schneller.

/*
 * Ausfalten von Dimensionen einer Liste über rotierende Ketten
 */
//______________________________________________________________________________
package allcombies;

//______________________________________________________________________________
/**
 * @author huckfinn
 */
public class Main {
    
    protected int[] data = {1,2,3,4};
    
    int dim=2;
    
    //__________________________________________________________________________
    
    class RotatingChain {
        int[] buffer = null;
        int firstItem = -1;
        boolean finished = false;
        RotatingChain child = null;
        
        //______________________________________________________________________
        public RotatingChain(int[] buffer) {
            this.buffer = new int[buffer.length];
            for (int i = 0; i < buffer.length; i++) this.buffer[i] = buffer[i];
            firstItem = this.buffer[0];
        }
        //______________________________________________________________________
        public void rotate() {
            int lastItem = buffer[buffer.length-1];
            for (int i = 1; i < buffer.length; i++) {
                buffer[buffer.length-i]=buffer[buffer.length-i-1];
            }
            buffer[0] = lastItem;
            if (firstItem==buffer[0]) doRotateChild();
        }
        //______________________________________________________________________
        public void doRotateChild() {
            if (child!=null) child.rotate();
            else finished = true; // Abbruchbedingung setzen
        }
        //______________________________________________________________________
        public void setChild(RotatingChain aChild) { child=aChild; }
        
    }
    
    //__________________________________________________________________________
    /** Konstruktor */
    public void run() {
        RotatingChain[] cb = new RotatingChain [dim];
        for (int i = 0; i < dim; i++) {
            cb [i]= new RotatingChain(data); // Initialisieren
            if (i>0) cb[i-1].setChild(cb[i]); // Verketten der "Digits" 
        }
        RotatingChain lastChain = cb[dim-1]; // Kette welche die 
                                             // Abbruchbdeingung enthält
        RotatingChain firstChain = cb[0];    // Kette die weitergezählz wird 
        
        // Überdiese Routine wird der gesamte Adressraum angesteuert 
        // ..alle Permutationen
        while (!lastChain.finished) {
            for (int i = 0; i < dim; i++) {
                    // Hier muß dein Filtercode rein wenn du Bedingungen 
                    // wegwerfen willst z.B. alle gleich
                    System.out.print(cb[i].buffer[0]);
            }
            System.out.println();
            firstChain.rotate();
        }
    }
    //__________________________________________________________________________
    /** Testrotine */
    public static void main(String[] args) {
        Main t = new Main(); t.run();
    }
}
//__EOF_________________________________________________________________________

Die Routine steuert lediglich den gesamte Adressraum an. Die Bedingungen die du haben willst mußt du entweder in der Schleife

            for (int i = 0; i < dim; i++) {
                    // Hier muß dein Filtercode rein wenn du Bedingungen 
                    // wegwerfen willst z.B. alle gleich
                    System.out.print(cb[i].buffer[0]);
            }

anbringen oder in der Rotationsregel des "Digits". Ok ich hoffe es hilft bis denne Huck

 

[huckfinn]

Ok weiter,

Du siehst, die Permutationen für dim=2 vollständig durchlaufen kann und für 3 bis N (der Kürze halber sei N = data.length).
Dabei wird der Suchraum wird nun sehr groß N^2+N^3..N^N. Man hat nun 2 Möglichkeiten am Code der den Suchraum durchforstet zu drehen.

1. In der Schleife z.B. alle gleichen Elemente sollen raus FILTER ..hier wird immer gerechnet und mit etwas vorher abgespeicherten verglichen und entschieden ob der Filter passt oder nicht
2. die Rotationsregel einer Kette . z.B. Relation der "Digits" untereinader. Hier kann man smart ansetzen und Rotationen so ansetzen (überspringen, ander Abbruchregel), daß nicht alle Tests durchgezogen werden.

Man müßte nun wissen wie deine Subsets gestaltet sein sollen (Permutation mit Wiederholung ..voller Suchraum/ ohne Wiederholung viel weniger). Sag mal welche bis denne Huck.

 

[huckfinn]

Hi,

Ich hab das ganze noch mal mit Referenzpointern Untersetz. Hier die Klassen und ein Test:

/*
 * RotatingChain.java
 * Created on 16. Oktober 2006, 09:33
 */

package alltwo;

/** @author huckfinn */
public class RotatingChain {
    
    private IntegerList alphabeth = null;
    private Integer firstItem   = null;
    private Integer lastItem    = null;
    private Integer currentItem = null;
    private int offset = 0;
    private boolean finished = false;
    private RotatingChain child  = null;
    
    /** Creates a new instance of RotatingChain */

    public RotatingChain(IntegerList alphabeth) {
        this.setAlphabeth(alphabeth);
        firstItem   = this.getAlphabeth().first();
        currentItem = this.getAlphabeth().get(getOffset());
        lastItem    = this.getAlphabeth().last();
    }
    
    public void rotate() {
        offset++;
        if (getOffset()>getAlphabeth().length()-1) {
            setOffset(0); doRotateChild();
        }
        currentItem = getAlphabeth().get(getOffset());
    }
    
    public void rotateLowerThanParent() {
        int chainCounter = 0;
        offset++;
        if (child==null) {
            if (getOffset()>getAlphabeth().length()-1) {
                offset=0;
                doRotateChild();
            }
        } else {
            boolean indexOverflow = getOffset()>getAlphabeth().length()-1;
            if (!indexOverflow) {
                RotatingChain p = this;
                RotatingChain c = child;
                while (c!=null) {
                int pi = p.getOffset();
                int ci = c.getOffset();
                if (pi>=ci) {
                    p.setOffset(0);
                    p.doRotateChild();
                    p=c; c=c.getChild();
                  } else c= null;
                } 
            } else {             
              setOffset(0);
              doRotateChild(); 
            }
        }
        currentItem = getAlphabeth().get(getOffset());
    }
    
    public void doRotateChild() {
        if (getChild()!=null) getChild().rotate(); // Rotiere die Kindkette
        else finished = true; // Abbruchbedingung für die letzte Kette setzen
    }
    
    public void setChild(RotatingChain aChild) { child=aChild; }
    
    public IntegerList getAlphabeth() { return alphabeth; }
    
    public void setAlphabeth(IntegerList alphabeth) { this.alphabeth = alphabeth;}
    
    public Integer getFirstItem() { return firstItem; }
    
    public Integer getLastItem() { return lastItem; }
    
    public Integer getCurrentItem() {  return currentItem;}
    
    public int getOffset() {  return offset; }

    public void setOffset(int aOffset) {  
        offset=aOffset;    currentItem = getAlphabeth().get(getOffset());
    }
    
    public boolean isFinished() { return finished; }
    
    public RotatingChain getChild() {   return child; }
}

Die InregerListe

/*
 * IntegerList.java
 * Created on 16. Oktober 2006, 10:17
 */

package alltwo;

import java.util.*;

/** @author huckfinn */
public class IntegerList {
    ArrayList data = null;
    //__________________________________________________________________________
    public IntegerList() { data = new ArrayList(); }
    public void add(int value) {data.add(new Integer(value));}
    public void set(int index, int value) { data.set(index,new Integer(value));}
    public Integer  get(int index) {
         return (Integer)data.get(index);
    }
    public void clear() { data.clear(); }
    public Integer first() { return get(0);}
    public Integer last()  { return get(length()-1); }
    public int length()    { return data.size(); }
    public int  getInt(int index) {
         Integer val = (Integer)data.get(index);
         return val.intValue();
    }
    public void sort () { Collections.sort(data); }
}

und der Test :

/*
 * Ausfalten von Dimensionen einer Liste über rotierende Ketten
 */
//______________________________________________________________________________
package alltwo;

import java.util.*;
//______________________________________________________________________________
/**
 * @author huckfinn
 */
public class Main {
    
    IntegerList alpha = null;
    
    int dim=2;
    
    //__________________________________________________________________________
    public void initAlphabet() {
        alpha = new IntegerList();
        alpha.add(0);
        alpha.add(1);
        alpha.add(3);
        alpha.add(7);
        alpha.add(11);
        alpha.add(13);
        alpha.add(17);
    }
    
    /** Hole alle Permutationen der Länge dim */
    public void runAll(int dim) {
        System.out.println("----- Alle Varianten der Länge "+dim+"-----");
        RotatingChain[] chain = new RotatingChain [dim];
        ArrayList result = new ArrayList();
        for (int i = 0; i < dim; i++) {
            chain[i]= new RotatingChain(alpha);  // Initialisieren
            if (i>0) chain[i-1].setChild(chain[i]); // Verketten der "Digits"
        }
        RotatingChain lastChain = chain[dim-1]; // Kette welche die
        // Abbruchbdeingung enthält
        RotatingChain firstChain = chain[0];    // Kette die weitergezählz wird
        
        // Überdiese Routine wird der gesamte Adressraum angesteuert
        // ..alle Permutationen
        while (!lastChain.isFinished()) {
            String s="";
            for (int i = 0; i < dim; i++) {
                // Hier muß dein Filtercode rein wenn du Bedingungen
                // wegwerfen willst z.B. alle gleich
                if (i<dim-1)
                  s = s+chain[i].getCurrentItem()+", ";
                else
                  s = s+chain[i].getCurrentItem()+"; ";
            }
            result.add(s);
            firstChain.rotate();
        }
        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) 
            System.out.println((String) result.get(i));
    }

    /** Hole alle Permutationen der Länge dim ohne Vertauschung */
    public void runCombi(int dim) {
        System.out.println("----- Alle Varianten ohne Wiederholung der Länge "+dim+"-----");
        alpha.sort();
        RotatingChain[] chain = new RotatingChain [dim];
        for (int i = 0; i < dim; i++) {
            chain[i]= new RotatingChain(alpha);  // Initialisieren
            if (i>0) chain[i-1].setChild(chain[i]); //  Verketten der "Digits"
        }
        RotatingChain lastChain = chain[dim-1]; // Kette welche die
        // Abbruchbdeingung enthält
        RotatingChain firstChain = chain[0];    // Kette die weitergezählt wird
        ArrayList result = new ArrayList();
        // Überdiese Routine wird der gesamte Adressraum angesteuert
        // ..alle Permutationen
        while (!lastChain.isFinished()) {
            String s="";
            for (int i = 0; i < dim; i++) {
                // Hier muß dein Filtercode rein wenn du Bedingungen
                // wegwerfen willst z.B. alle gleich 
                if (i<dim-1)
                  s = s+chain[i].getCurrentItem()+", ";
                else
                  s = s+chain[i].getCurrentItem()+"; ";
            }
            result.add(s);
            // System.out.println(s);
            firstChain.rotateLowerThanParent();
        }
        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) 
            System.out.println((String) result.get(i));
    }
    
    public Main() {
        initAlphabet();
        runCombi(alpha.length());
    }

    /** Testrotine */
    public static void main(String[] args) {
        Main t = new Main(); 
    }
    
}

Bis denn Huck