Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[VB/Delphi] wszystkie możliwe równania X zmiennych

janek1111 07 Lip 2010 18:12 1930 15
  • #1 07 Lip 2010 18:12
    janek1111
    Poziom 13  

    Witam

    Szukam jakieś książki (coś w tym rodzaju) w której byłby poruszany problem kombinatoryki pod kątem VB czy Delphi, dzięki której mógłbym rozwiązać podobny problem:

    Mam w dwóch listboxach kolejno podane w wierszach dane: a,b,c i w drugiej -,+. Danych w kolumnach może być więcej bądź mniej. Cały sprawa polega na tym aby z tych danych z tych kolumn ułożyć wszystkie możliwe równania (w tym przypadku ma być ich chyba 24). Wynik np. w trzecim listboxie byłby taki (niektóre równania by się powtarzały ale nie o to chodzi):

    a+b-c
    a-b+c
    a-b-c
    a+b+c
    a+c-b
    a-c-b
    a+c+b
    a-c+b

    b-c-a
    b+c+a
    b-c+a
    b+c-a
    b+a-c
    b-a+c
    b-a-c
    b+a+c

    c-a-b
    c+a+b
    c-a+b
    c+b-a
    c-b+a
    c-b-a
    c+b+a

    Mając np. więcej danych w obu kolumnach wyników będzie stosunkowo więcej. Za pomoc z góry dziękuję.

    Dodano po 1 [godziny] 7 [minuty]:

    Teraz zauważyłem, że jest błąd w ilości generowanych wyników. Napisałem, że ma być ich 24. Natomiast wg tego:

    [VB/Delphi] wszystkie możliwe równania X zmiennych

    Zdaje się, że ma być (2^2)*(2^3)=32, ale zabrakło by wtedy wyników, jak to ma być z tym wariacjami?

    Regulamin, p. 11. Temat poprawiłem.
    [Dr.Vee]

    0 15
  • #2 07 Lip 2010 19:04
    lanky
    Poziom 17  

    To zależy czy z powtórzeniami czy beż powtórzeń do tego dodaj sobie kombinacje plusa i minus. Jak się okazuje to kombinacji może być nawet powyżej setki.

    zrobiłem ci coś takiego:

    Code:

    var
    a,b,c: char;
    znakA, znakB: char;
    begin
    znakA:= '+';
    znakB:= '-';

    for a:= #65 to #67 do
    for b:= #65 to #67 do
    for c:= #65 to #67 do
    begin
       Memo1.Lines.Add(a+znakA+b+znakA+c);
       Memo1.Lines.Add(a+znakA+b+znakB+c);
       Memo1.Lines.Add(a+znakB+b+znakA+c);
       Memo1.Lines.Add(a+znakB+b+znakB+c);
    end;


    Sprawdz sobie to jeszcze bo robiłem to na szybkości :)

    0
  • #3 07 Lip 2010 21:37
    Dr.Vee
    VIP Zasłużony dla elektroda

    Zadanie możesz sobie uprościć albo utrudnić ;)

    Upraszczasz zakładając, że każda "zmienna" może występować w wyrażeniu tylko raz, a przed nią może wystąpić +1, -1 albo 0 (czyli brak zmiennej).
    W ten sposób masz wszystkie wyrażenia.

    Jeśli dopuścisz użycie innych operatorów, to sprawa się komplikuje - zwłaszcza gdy masz działania o różnej kolejności wykonywania (np. + i *) - wtedy kolejność zmiennych i znaków działań ma znaczenie.
    W tym przypadku najprościej byłoby wygenerować wszystkie możliwe działania i upraszczać je za pomocą kilku reguł w celu wyeliminowania równoważnych wyrażeń.

    0
  • #4 07 Lip 2010 22:30
    przemo_wielki
    Poziom 23  

    janek1111 napisał:

    Zdaje się, że ma być (2^2)*(2^3)=32, ale zabrakło by wtedy wyników, jak to ma być z tym wariacjami?


    Z tego co przedstawiłeś bardziej prawdopodobne jest 3!*2^2 = 24. Najpierw trzeba się określić ile będzie powtórzeń bo w tym przypadku mamy i 'pseudo-permutacje' i wariacje.

    Idąc dalej mamy permutacje bez powtórzeń dla a,b,c 3! =6
    {(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)} następnie dla każdej pary mamy odpowiednio 2^2 wariacji z powtórzeniami
    (a,b,c)++
    (a,b,c)+-
    (a,b,c)-+
    (a,b,c)--
    ...

    Jeżeli chodzi o algorytm dla całego przypadku to może być ciężko ale rozbijając na tworzenie wariacji i permutacji myślę że będzie trochę ławiej (choć mogę się mylić).

    0
  • #5 07 Lip 2010 23:19
    lanky
    Poziom 17  

    Po co wy się produkujecie?? przecież podałem rozwiązanie. jeśli chcecie na 24 to wystarczy zastosować filtr:

    Code:

    var
    a,b,c: char;
    znakA, znakB: char;
    begin
    znakA:= '+';
    znakB:= '-';

    for a:= #65 to #67 do
    for b:= #65 to #67 do
    for c:= #65 to #67 do
      if (a <> b) and (a <> c) and (b <> a) and (b <>c) then  // filtr ;)
        begin
          Memo1.Lines.Add(a+znakA+b+znakA+c);
          Memo1.Lines.Add(a+znakA+b+znakB+c);
          Memo1.Lines.Add(a+znakB+b+znakA+c);
          Memo1.Lines.Add(a+znakB+b+znakB+c);
        end;
    end;

    0
  • #6 08 Lip 2010 00:14
    marcinj12
    Poziom 40  

    Znalazłem i trochę przerobiłem - co prawda pod C# - algorytm z tego źródła - zwraca wszystkie permutacje tablicy char przez zamianę elementów:

    Code:

    private static void swap(char[] s, int a, int b)
    {
       char temp = s[a];
       s[a] = s[b];
       s[b] = temp;
    }

    private static bool permute(char[] str, int len)
    {
       int key = len - 1;
       int newkey = len - 1;

       /* The key value is the first value from the end which
          is smaller than the value to its immediate right        */

       while ((key > 0) && (str[key] <= str[key - 1]))
       { key--; }

       key--;

       /* If key < 0 the data is in reverse sorted order,
          which is the last permutation.                          */

       if (key < 0)
          return false;

       /* str[key+1] is greater than str[key] because of how key
          was found. If no other is greater, str[key+1] is used   */

       newkey = len - 1;
       while ((newkey > key) && (str[newkey] <= str[key]))
       {
          newkey--;
       }

       swap(str, key, newkey);

       /* variables len and key are used to walk through the tail,
          exchanging pairs from both ends of the tail.  len and
          key are reused to save memory                           */

       len--;
       key++;

       /* The tail must end in sorted order to produce the
          next permutation.                                       */

       while (len > key)
       {
          swap(str, len, key);
          key++;
          len--;
       }

       return true;
    }


    Wywołanie:
    Code:

    char[] test_string = new char[] {'a', 'b', 'c', 'd'};

    do
    {
       Console.WriteLine(test_string);
    }
    while (permute(test_string, test_string.Length));


    To by załatwiło sprawę różnych "kombinacji" pozycji zmiennych. Teraz tylko trzeba by przepisać wynik do 2x większej tablicy, pomiędzy sąsiednie zmienne wstawiając znak + lub -. Niestety ten algorytm nie permutuje poprawnie znaków + i -, a nie chce mi się myśleć nad nowym :) Możesz spróbować przerobić go na Delphi.

    A Koledze od "produkcji" lanky proponuję dokładniej przeczytać założenia autora lub choćby sam temat - wyraźnie napisał że kolumn może być więcej. Dla 3 zmiennych łatwo wypisać 4 linie tekstu z kombinacją znaków + i -, a dla 5 czy 8 też??

    0
  • #7 08 Lip 2010 09:59
    janek1111
    Poziom 13  

    Dziękuję za poruszenie tematu, mniej więcej dzięki temu rysuje mi się algorytm jak mam to zrobić w VB. Ale chciałbym powrócić do "wszystkich możliwych wyników". Co do pierwszego równania z danymi abc, i +-, przedstawiałem (mam nadzieję) wszystkie możliwe kombinację z tego przypadku. Chodzi mi o to, że dane a,b,c w jednym równaniu nie mogą się powtarzać, jedynie mogą + i - (oczywiście w grę wchodzi więcej danych w równaniu). Z tego wynika, że mój algorytm musi się opierać na tym o czym piesze przemo_wielki. Co do Delphiego ze względów technicznych jeszcze tego nie sprawdzałem.

    0
  • #8 08 Lip 2010 18:07
    janek1111
    Poziom 13  

    Mógłby ktoś przepisać te komendy na język C i ewtl. wysłać plik exe, bo nie znam w ogóle tego języka. Bo nie wiem czy VB jest taki wolny czy mój komp.

    If Option1.Value = True Then opcja = 99999
    If Option2.Value = True Then opcja = 299999
    If Option3.Value = True Then opcja = 399999
    If Option4.Value = True Then opcja = 499999
    If Option5.Value = True Then opcja = 599999
    If Option6.Value = True Then opcja = 999999
    If Option7.Value = True Then opcja = 999999
    znowu:
    List1.AddItem licznik
    licznik = licznik + 1
    If opcja = licznik Then GoTo koniec
    GoTo znowu
    koniec:

    0
  • #9 08 Lip 2010 20:48
    lanky
    Poziom 17  

    Wolno bo pokazujesz od razu liczby na ekranie.

    Code:

    List1.AddItem licznik

    załaduj sobie te liczby w jakiś bufor najlepiej.
    poza tym twój kod możesz zrobić w zwykłej pętli
    Code:

    for i:=0 to opcja do
    List1.AddItem i

    i to będzie to samo

    0
  • #10 08 Lip 2010 21:38
    janek1111
    Poziom 13  

    Z tym for:= i nie działa. Ale spróbowałem z zapisem danych bezpośrednio na dysk w pliku przez komendę print. Jest znacznie szybciej, ale czy nie będzie szybciej jak wynik tego będzie w buforze? Jeśli chodzi o bufory to jeszcze mi nie były potrzebne więc za dużo nie wiem na ten temat...

    0
  • #12 08 Lip 2010 23:15
    janek1111
    Poziom 13  

    Przepisałem to TU co Ty napiłeś dla jasności. W VB próbowałem na parę mi znanych sposobów i wynikiem nie była cała lista licznika tylko ostatnia liczba z licznika.

    Dodano po 58 [sekundy]:

    Dlatego pisałem wcześniej, że jestem słaby w buforach.

    0
  • #13 08 Lip 2010 23:56
    lanky
    Poziom 17  

    Cytat:

    Ale spróbowałem z zapisem danych bezpośrednio na dysk w pliku przez komendę print. Jest znacznie szybciej, ale czy nie będzie szybciej jak wynik tego będzie w buforze?

    To możesz potraktować jako bufor. Po co chcesz na raz wyświetlić tyle danych ? od 0 do 999999 to jest prawie 8mb.

    0
  • #14 09 Lip 2010 19:45
    janek1111
    Poziom 13  

    To z tym, licznikiem tylko dla sprawdzenia szybkości działania. Taki bufor jest mi potrzebny bo wstępny algorytm wykłada bardzo dużo wyników kombinacji (np. przy 9 danych i 4 danych w drugiej kolumnie, kombinacji będzie ok 5mln, ale to tylko abstrakcja na razie)...

    0
  • #15 09 Lip 2010 21:59
    lanky
    Poziom 17  

    No to niech będzie nawet 100 milionów ale nie musisz tego przecież wszystkiego wyświetlać.Wszystkie kombinacje możesz zapisywać do jakiegoś stringa albo kilku stringów i wyświetlać tylko pojedyncze bloki które będą cie interesowały.np string1 będzie przechowywał pierwszych tysiąc kombinacji string2 drugi tysiąc itd.

    0
  • #16 10 Lip 2010 09:22
    przemo_wielki
    Poziom 23  

    A nie lepiej wyniki przechowywać w pliku tekstowym?

    0