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

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

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

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

0

Dzięki serdeczne działa idealnie.

0

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

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

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.

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/questions/2685501/next-permutation-for-combinations-or-subsets-in-powerset

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

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

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

0
Shalom napisał(a):

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

Sorki mógłbyś jaśniej bo do końca nie rozumiem zrobiłem coś takiego ale nie działa

 #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,ofstream plik)
{
    if(numbersLeft>0)
    {
        for(set<int>::iterator it = ++lastValue; it!=valuesInSet.end(); it++)
        {
            valuesToPrint.push_back(*it);
            combination(valuesToPrint,valuesInSet,it,numbersLeft-1,plik);
            valuesToPrint.pop_back();
        }
    }
    else
    {
                
                
 
        for(vector<int>::iterator it=valuesToPrint.begin(); it!=valuesToPrint.end();it++)
        {
 
            plik<<*it<<" ";
            
        }
 
        cout<<endl;
        
    }
}
 
int main()
{
    set<int> valuesSet;
    for(int i=0;i<=5;i++)
    {
        valuesSet.insert(i);
    }
    vector<int> valuesToPrint;
    plik.open("a.txt");
    combination(valuesToPrint,valuesSet,valuesSet.begin(),3,plik);
    plik.close();
 
 
        return 0;
}
1

Czy ludzie dziś poważnie potrafią nawet ukraść gotowca z internetu? Aż mi słabo...

#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,ofstream& plik)
{
    if(numbersLeft>0)
    {
        for(set<int>::iterator it = ++lastValue; it!=valuesInSet.end(); it++)
        {
            valuesToPrint.push_back(*it);
            combination(valuesToPrint,valuesInSet,it,numbersLeft-1,plik);
            valuesToPrint.pop_back();
        }
    }
    else
    {
        for(vector<int>::iterator it=valuesToPrint.begin(); it!=valuesToPrint.end(); it++)
        {
            plik<<*it<<" ";
        }
        plik<<endl;
    }
}

int main()
{
    set<int> valuesSet;
    for(int i=0; i<=5; i++)
    {
        valuesSet.insert(i);
    }
    vector<int> valuesToPrint;
    ofstream plik("a.txt");
    combination(valuesToPrint,valuesSet,valuesSet.begin(),3,plik);
    plik.close();
    return 0;
}

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