Kombinacje x elementów bez powtórzeń ze zbioru n elementowego

2011-09-08 00:01
nobody
0

Temat pewnie nic nie mówi więc napisze tak
mam 2 liczby
n - liczba naturalna oznaczająca zakres np. 10
x - ilość wybranych elementów ze zbioru mniejsza od n np. 3
czyli mam zbiór
1,2,3,4,5,6,7,8,9,10
z którego chce wygenerować wszystkie możliwe kombinacje 3 elementów bez powtórzeń czyli
1,2,3
1,2,4
1,2,5
...
4,8,9
4,8,10
...

no i tutaj natrafiam na problem bo do głowy przychodzi mi mało optymalne rozwiązanie stworzyć sortowanie bąbelkowe, które wygeneruje wszystkie kombinacje, utnę część tablicy np. po 3 kolumnie zostaną mi wszystkie możliwe kombinacje i dopiero usunąć powtórzenia, ale wydaje mi się to bardzo nieoptymalne :/

ma ktoś pomysł na algorytm jak to uprościć?

edytowany 1x, ostatnio: madmike, 2016-12-13 18:26

Pozostało 580 znaków

2011-09-08 00:09
0

Rekurencyjnie?
Znasz zbiór, indeks ostatnio wylosowanego elementu, ilość liczb do wylosowania

  • jeśli do wylosowania jest jeszcze jakaś liczba
    • pętlisz się po elementach zbioru które są dalej niż ostatnio wylosowany element
    • wybierasz kolejne z tych liczb i wywołujesz funkcję z tym samym zbiorem, nowym indeksem i ilością liczb do wylosowania mniejszą o 1

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-09-08 01:17
nobody
0

nic z tego nie rozumiem czytałem to z 10 razy i dalej lipa - opisz to bardziej łopatologicznie, nie mam zamiaru losować liczb, tylko wypisać wszystkie możliwe kombinacje w których nie powtórzą się te same liczby w obojętnie jakiej kolejności

Pozostało 580 znaków

2011-09-08 02:11
1
#include <iostream>
#include <vector>
#include <set>
using namespace std;

void combination(vector<int>& valuesToPrint,set<int>& valuesInSet, set<int>::iterator currentValue, int numbersLeft)
{
    if(numbersLeft>0)
    {
        for(set<int>::iterator it = currentValue; it!=valuesInSet.end(); it++)
        {
            valuesToPrint.push_back(*it);
            set<int>::iterator next = it;
            next++;
            combination(valuesToPrint,valuesInSet,next,numbersLeft-1);
            valuesToPrint.pop_back();
        }
    }
    else
    {
        for(vector<int>::iterator it=valuesToPrint.begin(); it!=valuesToPrint.end();it++)
        {
            cout<<*it<<" ";
        }
        cout<<endl;
    }
}

int main()
{
    set<int> valuesSet;
    for(int i=0;i<10;i++)
    {
        valuesSet.insert(i);
    }
    vector<int> valuesToPrint;
    combination(valuesToPrint,valuesSet,valuesSet.begin(),3);
    return 0;
}

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2015-08-17 15:06
Dlaczego używasz seta jako valuesInSet, a nie wektora? Nie wykorzystujesz żadnych właściwości drzewa, a iteracja jest zdecydowanie wolniejsza. Dodatkowo valuesInSet powinno być przekazywane przez const referencję (taki dobry zwyczaj). - Zjarek 2011-09-08 12:11
Bo wykorzystuje matematyczne własności seta -> zawiera elementy niepowtarzajace się. Fakt, const tam być powinien. - Shalom 2011-09-08 12:13

Pozostało 580 znaków

2011-09-08 03:18
nobody
0

Dzięki serdeczne działa idealnie.

Pozostało 580 znaków

2011-09-08 08:29
0

A czy mógłby ktoś napisać to samo w Pascalu?

Pozostało 580 znaków

2011-09-08 09:53
0

do pascala nie zastosujesz raczej wektorów, ale możesz to zrobić na takiej zasadzie.
Masz tablicę 5 elementów: 1, 2, 3, 4, 5. Losujesz random pierwszą liczbę.
Wylosowana to 3. robisz swap wylosowanej liczby z ostatnią i tablica wygląda tak: 1, 2, 5, 4, 3. Zmniejszasz zakres randoma zeby losowal już nie od 0-4 tylko od 0-3. Wykonujesz tą samą operację, zostaje tablica 4, 2, 5, 1, 3. Jeszcze raz to samo: 4, 2, 5, 1, 3. I w ten sposób z tablicy 5 elementów od 1 do 5 wylosowane zostały 3 w kolejności 3, 1, 5.

PS: Swap powoduje naruszenie kolejności w tablicy, można użyć przy tym sortowania aby poukładać wartości, pamiętając aby nie sortować ostatniej pozycji w tablicy. (ale to nie jest konieczne).


Gdy się nie wie, co się robi, to dzieją się takie rzeczy, że się nie wie, co się dzieje ;-)

Pozostało 580 znaków

2011-09-08 11:51
0

MJay genialny z ciebie algorytmik, ale ciekawi mnie jak chcesz w ten sposób wypisać wszystkie kombinacje a nie tylko jedną losową...
Co do pascala to jaki problem? Wystarczy vector<> i set<> zmienic na tablicę + dodać argument z długością tej tablicy, iterator zamienić na numer indeksu,
Sam algorytm jest przecież identyczny.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
No cóż. Dla mnie to jest problem. - pelsta 2011-09-08 14:24
To ja chętnie, powiedzmy za 50zł, mogę przepisać to na pascala. Chętny? Zapraszam na priv. - Shalom 2011-09-08 14:34
Zwróć uwagę, że nie piszemy w dziale "praca". - pelsta 2011-09-08 14:45
Zwróć uwagę że prosisz o gotowca a nie o pomoc... - Shalom 2011-09-08 14:50
Zdarzyło mi się nie raz podesłać darmowego gotowca potrzebującym... Dobra. Poradzę sobie sam. - pelsta 2011-09-08 14:56

Pozostało 580 znaków

2011-09-08 13:48
0

Pod linkiem jest next_combination na wzor next_permutation z biblioteki standardowej c++. Wygląda dość złowrogo ale w pascalu chyba działa arytmetyka wskaźników? :-P

http://stackoverflow.com/ques[...]ations-or-subsets-in-powerset

Kod Shaloma jest dużo ładniejszy. :-)


"(...) otherwise, the behavior is undefined".
edytowany 1x, ostatnio: Endrju, 2011-09-08 13:49

Pozostało 580 znaków

2013-01-08 21:23
0

Sory a mogłby ktoś przerobić ten kod Shaloma aby wynik tego działania zapisywał do pliku bo mi się nie udaje a dopiero zaczynam przygodę z programowaniem o to mój pomysł(wstawiałem już w różne miejsce początek zapisu do pliku i zawsze zapisuje mi tylko ostatnią linijkę albo w ogóle ostatnią cyfrę):

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

void combination(vector<int>& valuesToPrint,set<int>& valuesInSet, set<int>::iterator lastValue, int numbersLeft)
{
    if(numbersLeft>0)
    {
        for(set<int>::iterator it = ++lastValue; it!=valuesInSet.end(); it++)
        {
            valuesToPrint.push_back(*it);
            combination(valuesToPrint,valuesInSet,it,numbersLeft-1);
            valuesToPrint.pop_back();
        }
    }
    else
    {
        ofstream plik;
        plik.open("a.txt")

        for(vector<int>::iterator it=valuesToPrint.begin(); it!=valuesToPrint.end();it++)
        {

            cout<<*it<<" ";
            plik<<*it<<endl;
        }

        cout<<endl;
        plik.cloe();
    }
}

int main()
{
    set<int> valuesSet;
    for(int i=0;i<=5;i++)
    {
        valuesSet.insert(i);
    }
    vector<int> valuesToPrint;
    combination(valuesToPrint,valuesSet,valuesSet.begin(),3);

    return 0;
}

Pozostało 580 znaków

2013-01-08 21:28
1

Otwórz plik przed wywołaniem funkcji combination(). Przekaż do tej funkcji obiekt ofstream. Wewnątrz funkcji tam gdzie był cout<< daj plik<<


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0