Pytanie n-ta lub arbitralna kombinacja dużego zestawu


Powiedz, że mam zestaw liczb od [0, ....., 499]. Kombinacje są obecnie generowane sekwencyjnie za pomocą C ++ std::next_permutation. Dla porównania rozmiar każdej krotki, którą wyciągam, wynosi 3, więc zwracam wyniki sekwencyjne, takie jak [0,1,2], [0,1,3], [0,1,4], ... [497,498,499].

Teraz chcę zrównoleglić kod, w którym się znajduje, więc sekwencyjne generowanie tych kombinacji przestanie działać. Czy istnieją jakieś algorytmy do obliczania ith kombinacja 3 od 500 liczb?

Chcę się upewnić, że każdy wątek, niezależnie od iteracji pętli, może obliczyć niezależną kombinację opartą na i iteruje z. Więc jeśli chcę tę kombinację i=38 w wątku 1 mogę obliczyć [1,2,5] podczas jednoczesnego przetwarzania i=0 w wątku 2 jako [0,1,2].

EDYTOWAĆ Poniższe stwierdzenie nie ma znaczenia, pomieszałem się

Przyjrzałem się algorytmom, które wykorzystują silniki do zawężania poszczególnych elementów od lewej do prawej, ale nie mogę ich użyć jako 500! na pewno nie zmieści się w pamięci. Jakieś sugestie?


12
2018-02-25 01:43


pochodzenie


Pokaż nam obliczenia dotyczące silni. Możesz po prostu patrzeć na to źle. Na pewno podzielisz jedną silnię na drugą, co zwykle oznacza, że ​​możliwe jest uproszczenie. - paddy
Myślę, że muszę przeformułować moje pytanie. To nie tylko permutacja 500 liczb. Jest to połączenie 3 na 500 możliwych. Ale chcę być w stanie wybrać dowolną kombinację spośród 500 wybierz 3 możliwe. - bgoers
Być może coś takiego: code.google.com/p/strtk/source/browse/trunk/strtk.hpp#11622 - Gerdiner
@Gerdiner, jeśli mógłbym zaakceptować odpowiedź od ciebie, zrobiłbym to. Ten kod jest bardziej ogólny i działa dokładnie tak, jak potrzeba. Świetny algorytm. Dziękuję Ci! - bgoers


Odpowiedzi:


Oto moje ujęcie:

int k = 527; //The kth combination is calculated
int N=500; //Number of Elements you have
int a=0,b=1,c=2; //a,b,c are the numbers you get out

while(k >= (N-a-1)*(N-a-2)/2){
    k -= (N-a-1)*(N-a-2)/2;
    a++;
}
b= a+1;
while(k >= N-1-b){
    k -= N-1-b;
    b++;
}

c = b+1+k;


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result

Rozumiemy, ile kombinacji istnieje, dopóki nie zwiększy się kolejna liczba. Jednak działa tylko dla trzech elementów. Nie mogę zagwarantować, że jest poprawny. Byłoby fajnie, gdyby porównać to do wyników i dać trochę informacji zwrotnych.


5
2018-02-25 02:38



Prosty, szybki, działa na tyle, na ile mogę to stwierdzić. Próbowałem wymyślić coś podobnego do tego, co napisał Jacobm, ale to lubię! - bgoers


Jeśli szukasz sposobu na uzyskanie indeksu leksykograficznego lub rangi unikalnej kombinacji zamiast permutacji, to twój problem mieści się w dwumianowym współczynniku. Współczynnik dwumianowy rozwiązuje problem wyboru unikalnych kombinacji w grupach K z całkowitą liczbą N elementów.

Napisałem klasy w języku C # do obsługi typowych funkcji do pracy ze współczynnikiem dwumianowym. Wykonuje następujące zadania:

  1. Wyprowadza wszystkie indeksy K w ładnym formacie dla dowolnego N wybiera K do pliku. Indeksy K można zastąpić bardziej opisowymi łańcuchami lub literami.

  2. Przekształca indeksy K w odpowiedni indeks leksykograficzny lub pozycję w sortowanej tabeli współczynników dwumianowych. Ta technika jest znacznie szybsza niż starsze opublikowane techniki, które opierają się na iteracji. Czyni to za pomocą właściwości matematycznych związanych z trójkątem Pascala i jest bardzo wydajne w porównaniu do iteracji przez zestaw.

  3. Konwertuje indeks w posortowanej tabeli współczynników dwumianowych na odpowiednie indeksy K. Uważam, że jest również szybszy niż starsze rozwiązania iteracyjne.

  4. Używa Mark Dominus metoda obliczania współczynnika dwumianowego, która jest znacznie mniej prawdopodobna do przepełnienia i działa z większymi liczbami.

  5. Klasa jest napisana w .NET C # i zapewnia sposób zarządzania obiektami związanymi z problemem (jeśli istnieją) za pomocą ogólnej listy. Konstruktor tej klasy przyjmuje wartość bool zwaną InitTable, która gdy true tworzy ogólną listę do przechowywania obiektów do zarządzania. Jeśli ta wartość jest nieprawidłowa, to nie utworzy ona tabeli. Tabeli nie trzeba tworzyć, aby móc korzystać z 4 powyższych metod. Dostępne są metody dostępu do tabeli.

  6. Istnieje skojarzona klasa testowa, która pokazuje, jak korzystać z klasy i jej metod. Został on szeroko przetestowany w 2 przypadkach i nie ma znanych błędów.

Aby przeczytać o tej klasie i pobrać kod, zobacz Tablizowanie Dwumianowy Coeffieicent.

Poniższy testowy kod będzie sprawdzał każdą unikalną kombinację:

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 500;  // Total number of elements in the set.
   int K = 3;  // Total number of elements in each group.
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination.  
      BC.GetKIndexes(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

Powinieneś być w stanie przenieść tę klasę dość łatwo do C ++. Prawdopodobnie nie będziesz musiał przechodzić przez ogólną część klasy, aby osiągnąć swoje cele. Twój testowy test 500 wybiera 3 zbiory 20 70 500 unikalnych kombinacji, które mieszczą się w 4-bajtowej int. Jeśli 500 wybierz 3 jest po prostu przykładowym przypadkiem i musisz wybrać kombinacje większe niż 3, będziesz musiał użyć długich lub być może stałego punktu int.


1
2018-02-25 02:37



Na pewno się tym zajrzę. 500 wybierz 3 jest najgorszym przypadkiem dla parametrów, których szukamy, więc nie martwię się zbytnio o przepełnienia. - bgoers


Możesz opisać konkretny wybór spośród 3 spośród 500 obiektów jako potrójny (i, j, k), gdzie i jest liczbą od 0 do 499 (indeks pierwszego numeru), j waha się od 0 do 498 (indeks drugiego, przeskakując nad tą liczbą, która była pierwsza), oraz k waha się od 0 do 497 (indeks ostatniego, pomijając obie poprzednio wybrane liczby). Biorąc to pod uwagę, w rzeczywistości dość łatwo jest wyliczyć wszystkie możliwe selekcje: zaczynając od (0,0,0), inkrementacja k aż osiągnie maksymalną wartość, a następnie zwiększyć j i zresetuj k do 0 i tak dalej, do j osiąga maksymalną wartość, i tak dalej, aż do j osiąga swoją maksymalną wartość; następnie zwiększaj i i zresetuj oba j i k i kontynuuj.

Jeśli ten opis brzmi znajomo, dzieje się tak, ponieważ działa dokładnie tak samo, jak numer bazowy 10 działa, z tym że baza jest znacznie bardziej zabawna, a w rzeczywistości baza różni się od cyfry do cyfry. Możesz użyć tego wglądu, aby zaimplementować bardzo kompaktową wersję idei: dla dowolnej liczby całkowitej n od 0 do 500 * 499 * 498, możesz uzyskać:

struct {
  int i, j, k;
} triple;

triple AsTriple(int n) {
  triple result;
  result.k = n % 498;
  n = n / 498;
  result.j = n % 499;
  n = n / 499;
  result.i = n % 500;  // unnecessary, any legal n will already be between 0 and 499
  return result;
}

void PrintSelections(triple t) {
  int i, j, k;
  i = t.i;
  j = t.j + (i <= j ? 1 : 0);
  k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0);
  std::cout << "[" << i << "," << j << "," << k << "]" << std::endl;
}

void PrintRange(int start, int end) {
  for (int i = start; i < end; ++i) {
    PrintSelections(AsTriple(i));
  }
}

Teraz, aby odłożyć, możesz po prostu wziąć liczby od 0 do 500 * 499 * 498, podzielić je na podzbiory w dowolny sposób, a każdy fragment wyliczać permutację dla każdej wartości w jej podzakresie.

Ta sztuczka jest bardzo przydatna w przypadku każdego problemu, w którym należy wyliczyć podzbiory.


0
2018-02-25 02:25



Jedynym problemem jest to, że skończyłbym z powielaniem. Potrzebuję 500 kombinacji 3 (najgorszy przypadek), czyli około 20 milionów kombinacji. Dzieje się to bez powielania, więc (0,0,0) jest wyeliminowane. Dziękuję, doceniam odpowiedź! - bgoers
Nie, nie ma duplikacji tak jak to opisałem. Sztuczka polega na interpretacji: (0,0,0) reprezentuje pierwszy, drugi i trzeci element, ponieważ dla każdego numeru pomijasz wszystkie elementy, które już wybrałeś. - jacobm
Ahhhh. Teraz widzę. Przetestuję to trochę! - bgoers
FYI, zaktualizował powyższy przykład kodu, aby był bardziej kompletny i mam nadzieję, że wyjaśnię sposób, w jaki liczby są interpretowane nieco. - jacobm
Ta odpowiedź jest niepoprawna. Możesz to łatwo zobaczyć, wywołując PrintRange (0, 1). Wyświetla [0,1,1], co nie jest nawet poprawną kombinacją. Produkuje również wiele duplikatów. Na przykład mapuje 1 do [0,1,2] i 498 do [0,2,1]. Prawidłowe rozwiązanie tego problemu wymaga bardziej skomplikowanych obliczeń. - peastman