Kombinations Algorithmus

Re(19): Kombinations Algorithmus

Penguin — Tue, 18 Nov 2003 01:02:52 GMT

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.

Re(18): Kombinations Algorithmus

mar99 — Tue, 18 Nov 2003 00:11:26 GMT

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

mar99

Re(6): Kombinations Algorithmus

Penguin — Tue, 18 Nov 2003 00:06:42 GMT

danke!

Re(5): Kombinations Algorithmus

hariw — Tue, 18 Nov 2003 00:03:24 GMT

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

Re(4): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:54:57 GMT

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

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:54:00 GMT

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

dachte eigentlich es geht einfacher auch

Re(3): Kombinations Algorithmus

hariw — Mon, 17 Nov 2003 23:52:16 GMT

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

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:47:37 GMT

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.

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:46:02 GMT

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

Re(4): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:44:45 GMT

sorry für die späte antwort

darf alles verwenden was ich in vba danach umsetzen kann.

Re(17): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 23:43:37 GMT

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.

Re(16): Kombinations Algorithmus

mar99 — Mon, 17 Nov 2003 23:09:19 GMT

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

Re(2): Kombinations Algorithmus

britta — Mon, 17 Nov 2003 22:30:16 GMT

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

Re(7): Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 22:29:55 GMT

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)

Re(2): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 22:29:40 GMT

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

Re: Kombinations Algorithmus

hariw — Mon, 17 Nov 2003 22:29:25 GMT

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

Re: Kombinations Algorithmus

britta — Mon, 17 Nov 2003 22:27:26 GMT

!!! 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;
}

Re(15): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 22:27:13 GMT

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

Re(2): Kombinations Algorithmus

mar99 — Mon, 17 Nov 2003 22:13:35 GMT

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

Re: Kombinations Algorithmus

fhauser — Mon, 17 Nov 2003 22:05:09 GMT

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

Re(3): Kombinations Algorithmus

mar99 — Mon, 17 Nov 2003 21:36:56 GMT

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

Re(6): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 21:20:38 GMT

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?

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 21:18:06 GMT

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...

Re(14): Kombinations Algorithmus

mar99 — Mon, 17 Nov 2003 20:57:45 GMT

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

Re(14): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 20:54:42 GMT

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

Re(13): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 20:52:26 GMT

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

Re(12): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:46:32 GMT

rekursion

Re(11): Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 20:39:12 GMT

allgemein rekursion oder das da?

Re(10): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:38:38 GMT

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

Re(9): Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 20:37:12 GMT

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

Re(8): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:35:13 GMT

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????

Re(7): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 20:27:57 GMT

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

Re: Kombinations Algorithmus

mar99 — Mon, 17 Nov 2003 20:27:29 GMT

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

Re(5): Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 20:26:50 GMT

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?

Re(6): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:18:13 GMT

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.

Re(5): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 20:13:51 GMT

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

Re(4): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:12:00 GMT

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

Re(4): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 20:11:15 GMT

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.

Re(3): Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 20:06:06 GMT

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

Re(3): Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 20:01:44 GMT

und die werte einfach nur ausgeben auf die Standardausgabe?

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 19:55:58 GMT

nein

Re(2): Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 19:55:45 GMT

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?

Re: Kombinations Algorithmus

komplexler — Mon, 17 Nov 2003 19:55:06 GMT

ist die laufzeit relevant?

Re: Kombinations Algorithmus

Somnatic — Mon, 17 Nov 2003 19:42:01 GMT

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

Kombinations Algorithmus

Penguin — Mon, 17 Nov 2003 19:38:12 GMT

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!