Kombinations Algorithmus

Kombinations Algorithmus (49 Beiträge, 321 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Hallo,

ich brauch einen Algorithmus der folgendes macht:

aus einer Kombination von Variablen (beliebig viele), von denen jede 2 Zustände kennt, sollen jetzt alle Kombinationen dieser Zustände ausgegeben werden.
die Grundzustände sind für alle gleich (ein/aus), allerdings ist ein Wert immer gesetzt.

Also zB:
Variable 1: Zustand 1
Variable 2: Zustand 1
Variable 3: Zustand 0

Der Zustand ist nur von geringer Bedeutung, ich will jetzt folgende Kombinationen:
V1=0, V2=0, V3=0
V1=0, V2=0, V3=1
v1=0, v2=1, v3=0
v1=0, v2=1, v3=1
v1=1, v2=0, v3=0
v1=1, v2=1, v3=0
v1=1, v2=0, v3=1
v1=1, v2=1, v3=1

v1 heißt Variable 1 etc.

Steh irgendwie auf der Leitung, bzw. komm nicht dahinter wie ich das dem Programm beibringen soll.

Danke auf jeden Fall!

mfg

Penguin

klingt für mich nach einer rekursiven lösung ...

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

in einfachen worten?

ich weiß dass ich immer 2 hoch x (wobei x die Nummber der Variablen) Möglichkeiten habe, nur wie schließe ich im Algorithmus die gleichen Sachen aus?

mfg

Penguin

inwiefern die gleichen sachen ...

ich glaube ich verstehe die aufgabenstellung nicht ...

da du im endeffekt ja nur schleifen durchgehst kann ja gar kein wert 2x entstehen

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

ok ich denk ich steh wirklich auf der leitung.

Wiederholende Werte sind auszuschliessen, mir ist trotzdem keine Schleifen-Kombination klar um das Ergebnis zu erzielen.

mfg

Penguin

ich lass da mal den komplexler weiter unten weitermachen ...
ich glaub ich versteh die aufgabenstellung nicht ganz ...

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

ich versuchs noch einmal, sorry wenn ich mich unklar ausdrücke

ich habe x variable die 2 zustände (1 und 0) haben können.

Die Zahl der möglichen Kombinationen ergibt sich aus 2 hoch x.

Jetzt möchte ich mir mit einem Algorithmus diese Möglichkeiten berechnen lassen, bzw. erstellen lassen, wobei das System flexibel bleiben, d.h. für jede (kleiner 50) Zahl funktionieren soll.

Bei 3 Variablen hätte ich also 8 Möglichkeiten,
bei 4 hätte ich 16
bei 5 hätte ich 32
etc.

die Anzahl kenn ich, aber die tatsächlichen Kombinationen möchte ich wissen.

mfg

Penguin

for (int i = 0; i < 2; i++) {
  for (int j = 0; j < 2; j++) {
    for (int k = 0; j < 2; k++) {
      System.out.println(i + " " + j + " " + k);
    }
  }
}

so würdest du zuerst
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
ausgaben bekommen ...

wenn du nun beliebig viele willst, dann müsstest du das ganz halt rekursiv programmieren ...

ich hab das oben jetzt nur mal so getippt, ausprobiert hab ichs nicht ..

aber wie du siehst entstehen hier keine doppelten ausgaben

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

hm...

zu überschwänglich, dass passt ja nur für drei, das mit dem rekursiv ist mir fern, soll ich code schreiben, der code erzeugt, wobei ich könnte doch die funktion einfach n mal ineinander aufrufen????

mfg

Penguin

glaubst nicht, dass rekursion einfacher ist als code zu erzeugen?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

ich wollte damit zum ausdruck bringen, dass ich nicht 100%ig verstehe was du meinst...

mfg

Penguin

allgemein rekursion oder das da?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

rekursion

mfg

Penguin

eine rekursive methode ist eine methode die sich selbst wieder aufruft ...

dabei muss aber zwingend eine Abbruchbedingung existieren .. das eigentliche problem ist nun diese zu finden

im endeffekt hast du dann aber eine methode z.b. abc, die wieder die methode abc aufruft ...

z.b.

du müsstest also nur eine einzige for schleife in einer methode machen, und in dieser for schleife würde sich diese methode dann wieder aufrufen (und dort wieder eine for schleife ausfhren).

Jedoch ist meist das Problem eine korrekte Abbruchbedingung zu finden .. und da ich das hasse, überlass ich es gern anderen

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

http://forum.geizhals.at/t208210,1154990.html#1154990

der komplexler hat die eh schon eine derartige lösung vorgestellt ...

theoretisch könnts so gehen .. ausprobiert hab ichs jedoch nicht

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

Was spricht wirklich gegen so etwas: http://forum.geizhals.at/t208210,1154993.html#1154993, noch dazu wo er anscheinend nur einen Pseudo Algo braucht.

Bezüglich Rekursion - so schwer wäre es auch nicht da man sogar die max Rekursionstiefe bereits zu Beginn kennt. Wie die 1er und 0er abgewechselt gehören wäre auch nicht das Problem (aber trotzdem aufwändiger als meine Lösung *gggg*).

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

gefällt mir recht gut

aber ich denke mir wenn er eine derartige aufgabenstellung hat, dann wird der lehrer/professor/wasauchimmer wohl etwas rekursives suchen

zumindest klingt es für mich schon stark danach ...

aber die bitweise addition hätte was interessantes

wär wahrscheinlich einfacher als über rekursion

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

Man kann ja auch ganz normal addieren und sich dann die Bitrepresentation ansehen. Je länger ich mir das ansehe desto schneller wird das in meinen Augen *gg*

@Rekursion - ja, nur rückt er nicht wirklich raus, was er (genau) machen soll bzw. was zuvor im "Unterricht" gelernt wurde.

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

das is leider für keinen Unterricht, um genau zu sein will ich ein System zur Abgrenzung von Fuzzy Mengen machen, nun muss ich aber auch die Kombinationen der Abgrenzungen berücksichtigen.

Da das ganze in Excel, sprich VBA programmiert ist, bin ich zudem ein wenig limitiert, was die Funktionalität betrifft.

mfg

Penguin

"Kombinationen der Abgrenzung" sagt mir nix. Aber Fuzzy und Excel - irgendwie sind das für mich 2 Begriffe die absolut nicht zusammen passen

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

wieso, grad in Excel lässt sich das herrlich modellieren.

Mir sind eher diese Special-Fuzzy Programme ein bisschen zu strange, die schauen aus als könntens 10x mehr als man braucht, aber verwenden kann man gar nichts weils entweder schlecht erklärt oder einfach unausgereift sind.

mfg

Penguin

ist die laufzeit relevant?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

nein

mfg

Penguin

und die werte einfach nur ausgeben auf die Standardausgabe?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

naja im Endeffekt werden die Werte dann zu gewiesen, d.h. ich will sie noch weiterverwenden, bzw. sie in Variablen speichern.

mfg

Penguin

algorithmus getVariations (v[n], i)
{
   if (i<=n)
   {
       v[i]=0;
       getVariations(v[1],...,v[n],i+1);

       v[i]=1;
       getVariations(v[1],...,v[n],i+1);
  }
   else
{ //print array
}

}

so irgendwie vielleicht?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

könntest du mir den code noch eimal erklären? ich versteh die Symbolik nicht ganz, in Worten:

wenn i kleiner gleich n

v[i] (als Array gedacht?)=0

rufe die funktion auf (welche werte übergebe ich?)

v[i]=1
rufe die funktion auf

ich versteh nicht wie das funktionieren soll, was übergebe ich beim aufrufen und wo zählt die Variable rauf?

mfg

Penguin

naja,
also am anfang habe ich ein array mit den werten.
das wird dann aufgerufen mit getVariations(array[],0)

im ersten schritt wird der erste (i) wert einmal auf 1, einmal auf 0 gesetzt.
dann rufe ich die methode rekursiv auf, mit i=i+1, somit wird der zweite wert bearbeitet, da setze ich wieder den wert einmal auf 1, einmal auf 0, das immer so weiter. abbruchbedingung: alle werte schon gesetzt. (i<=n)

(habs aber nicht getestet)

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

Also ich würde das auf Bit(vector) Basis machen. Wenn du 3 Variablen hast brauchst du einfach 3 Bits, diese beginnen mit 000 --> v1=0 (also bit an der Stelle 0), v2=0(also bit an der Stelle 1), v3=0(also bit an der Stelle 2), dann addierst du zu dem Wert einfach 1 --> 001 --> v1=1 (also bit an der Stelle 0), v2=0(also bit an der Stelle 1), v3=0(also bit an der Stelle 2) --> wieder 1 addieren, ... (und das 2^n mal machen)

Vielleicht gibts ne performantere Lösung (Komplexität O(2^n) (oder *g*), aber das spielt ja angeblich keine Rolle).

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

ohne mich jetzt ganz dumm stellen zu wollen, kannst du mir das noch einmal im detail erklären?

die wichtigsten fragen:

1) wie lasse ich offen, aus wie vielen Werten der Vektor besteht
2) wie zähle ich die Sachen hinzu (000 + 1 ist von mir aus 001, aber dann weiter?)

danke, die lösung scheint mir ehrlich gesagt noch verständlicher als das mit der rekursion...

mfg

Penguin

zu 1. - du mußt zu Beginn sowieso wissen, für welches n du das berechnen willst, genau hier hat man die Länge des Vektors (oder welche Datenstruktur man auch immer wählt).

Sagen dir Binärzahlen etwas? (ich hoffe, da hierrauf die Idee basiert *g*)
also, 000b = 0d [b=binär, d= dezimal]
001b = 1d
010b = 2d
011b = 3d
100b = 4d
101b = 5d usw.
(also 000+1=001
001 + 1 = 010
010 + 1 = 011
011 + 1 = 100 usw.

es genügt also das man zur Zahl immer 1 hinzufügt, wenn man sich dann die binäre Representation ansieht, so kommt man genau auf das Schema das du brauchst.

Welchen Algo brauchst du genau (Pseudoalgo, was darf verwendet werden? usw.)

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

sorry für die späte antwort

darf alles verwenden was ich in vba danach umsetzen kann.

mfg

Penguin

Einfacher wirds wenn du es nach Variablen aufbaust:

V0 wechselt 01010101
V1 wechselt 00110011
V2 wechselt 00001111
Vn wechselt (2^n) * zustand "0" dann (2^n) * zustand "1"

und das alles bis 2^(nmax+1) stellen

Wirds da wirklich einfacher? Wie kann er diese Ausgabe für n Variablen so erzeugen? (speziell in der Form in der er es braucht!) (Achtung, ist dann nicht mehr ganz so einfach)

mar99

Das ist der ganze Jammer, die Dummen sind immer so sicher und die Gescheiten so voller Zweifel.
[Bertrand Russell]

!!! Rekursion ist folgendes: !!!

printf("%ld\n",fac(10));

long fac(long argument)
{
if(argument<0) return -1; /* mathematischer Fehler */
if(argument==0) return 1; /* Ende der rekursiven Faktorierung erreicht */

return argument * fac(argument-1); /* "Funktion fac"´s erneuter Aufruf ihrerselbst */
}

<<---------------------------------->>
>>----Was tatsächlich gemeint ist----<<
<<---------------------------------->>

!!! Was gesucht ist in Deinem Beispiel und Wunsch ist die Zählung von Zahlen im Bereich von 0 bis x, wobei x sich aus 2^n - 1 ermittelt und n die Anzahl von Variablen ist, die die Zustände 0 oder 1 annehmen können. !!!

Die Lösung in einem C-Programm schaut so aus:

#include
#include

int main (void)
{
int n,bit;
int *pv,*p_bit;
long anzahl,zaehlerstand;

printf("Wieviele Variablen soll es geben, bitte um Ihre Eingabe (1-50) > ");
scanf("%d",&n);

if(n<1 n/>50)
{
printf("Die Eingabe liegt außerhalb des gültigen Wertebereichs von 1 und 50\n");
return -1;
}

pv= malloc(sizeof(int)*n); /* Speicher reservieren für v_array, Anfangsadresse des Integerarrays in pv Zeigervariable abspeichern */

/* v[i] für alle i von 0 bis n-1 auf Null setzen */
for(p_bit=pv,bit=0;bit0;anzahl--)
{

/* für jeden Zählerstand alle Bits (=Null/Eins Variablen) abarbeiten von 0 bis n-1 */
for(zaehlerstand=anzahl,p_bit=pv,bit=n-1;bit>=0;bit--)
{
  *p_bit++= zaehlerstand % 2;
  zaehlerstand >>= 1; /* durch 2 dividieren = den Wert um ein Bit nach rechts schieben */

  meine_funktion_die_mit_v_array_arbeitet(pv,n); /* Übergabe der Startadresse des Arrays der int Variablen an die Funktion */
}
}

return 0;
}

ich befürchte dass du ihn mit den memory allocations und die schiebereien jetzt vollkommen verwirrt hast

würde ich nicht schon länger programmieren (auch in ASM) hätt ichs nicht verstanden

<sing> Oh - thinking about the younger years </sing>
10 LOAD "SCISSORS"
20 RUNSee ? Sharp !

die beiden includes sind stdio.h und math.h, ist offensichtlich ein Blog Fehler ...

ah ja, weißt du ich bin versucht es verstehen zu wollen, aber da ich ein wengerl unter zeitdruck stehe, werd ichs mir erst ein wenig später zu gemüte führen

mfg

Penguin

nicht ganz ernst nehmen, nur ist mir das echt schon fast ein bisschen zu hoch

dachte eigentlich es geht einfacher auch

mfg

Penguin

hi,

in vb, nicht rekursiv..., mit wirren variablennamen

ergebnis ist im array Variables...

Sub getVariations()
    Dim a As Integer
    Dim x As Integer
    Dim i As Integer
    Dim j As Integer
    Dim z As Integer
    Dim counter
    Dim varNumber

    varNumber = 7   'könnte übergeben werden

    a = varNumber - 1
    x = 2 ^ varNumber - 1

    Dim Variables() As Integer
    ReDim Variables(varNumber - 1)

    For i = 0 To varNumber - 1
        Variables(i) = 0
    Next

    For i = 0 To x
        z = i
        For j = a To 0 Step -1
            If z / 2 ^ j >= 1 Then
                Variables(j) = 1
                z = z - 2 ^ j
            ElseIf z / 2 ^ j < 1 Then
                Variables(j) = 0
            End If
        Next
    'da kannst jeweils auf vars(j) zugreifen
    Next
End Sub

lg,
hariw
_________________________________________________________________________

The best way to speed up a PC is @ 9.81 m/sec².

danke, leider ist eine der wichtigsten Eigenschaften allerdings die, dass die Anzahl der Variablen, daher auch die Anzahl der Kombinationen, unbekannt ist, d.h. können je nach Usereingabe unterschiedlich sein.

Also heißt das die Anzahl der Möglichkeiten ist stets: 2 hoch x, daher kann ich das nicht so machen, trotzdem danke.

mfg

Penguin

hi,

guckst du die zeile...
>    varNumber = 7   'könnte übergeben werden

sub main()
  dim fritz as integer
  fritz = 9
  getVariations(fritz)
end sub

Sub getVariations(varNumber as integer)
.
.
.
.

lg,
hariw
_________________________________________________________________________

The best way to speed up a PC is @ 9.81 m/sec².

ups, war schon ganz verwirrt von den anderen ...

mfg

Penguin

hi,

nachdem´st es eh in vba "umsetzten willst"

copy - paste - enjoy

Sub main()
  Dim fritz As Integer
  fritz = InputBox("Anzahl der Bit´s!")
  getVariations (fritz)
End Sub

Sub getVariations(varNumber As Integer)
    Dim a As Integer
    Dim x As Integer
    Dim i As Integer
    Dim j As Integer
    Dim z As Integer
    Dim counter

    a = varNumber - 1
    x = 2 ^ varNumber - 1

    Dim Variables() As Integer
    ReDim Variables(varNumber - 1)

    For i = 0 To varNumber - 1
        Variables(i) = 0
    Next

    For i = 0 To x
        z = i
        For j = a To 0 Step -1
            If z / 2 ^ j >= 1 Then
                Variables(j) = 1
                z = z - 2 ^ j
            ElseIf z / 2 ^ j < 1 Then
                Variables(j) = 0
            End If
        Next
    'da kannst jeweils auf vars(j) zugreifen
    Next
End Sub

lg,
hariw
_________________________________________________________________________

The best way to speed up a PC is @ 9.81 m/sec².

danke!

mfg

Penguin

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung