Tüm olası kombinasyon. Daha hızlı yol

3 ile 1.000.000 arası değerler alabilen 1 ile 100 arasında bir sayıya (bu önemli değil) sahip bir vektörüm var.

Herhangi biri bu vektörden 3 değer benzersiz * kombinasyon elde etmeme yardımcı olabilir.

*Benzersiz

Örnek: Dizide aşağıdaki değerler var: 1 [0] 5 [1] 7 [2] 8 [3] 7 [4] ([x] indeks)

Bu durumda 1 [0] 5 [1] 7 [2] ve 1 [3] 5 [1] 7 [4] farklıdır, fakat 1 [5] [1] 7 [2] ve 7 [2] 1 [0] 5 [1] aynı (çift)

Çok fazla değerle çalıştığımda algoritmam biraz yavaş (örnek 1.000.000). Yani istediğim daha hızlı bir şekilde yapmak.

           for(unsigned int x = 0;x
1
1.000.000 değer 1.000.000 * 999,999 * 999,998/6 benzersiz kombinasyona sahiptir. Bu kombinasyonların her birini anında alsanız bile, sadece onlara bakmak sonsuza dek sürecektir!
katma yazar Shahbaz, kaynak
İndeks [3] bu örnekte 8 değerine sahip değil mi?
katma yazar Shahbaz, kaynak
Amacınız mümkün olan her bir kombinasyonun elde edilmesini sağlamak mı? 10 ^ 9 değeriniz varsa, test etmek için 10 ^ 27/3 kombinasyonları ile sonuçlanırsınız. Birçok kez pahalı olabileceğini "düşünmek" ...
katma yazar Brian, kaynak
Sayıların 1-100 arası olması önemli değil mi?
katma yazar r15habh, kaynak
1 [0] 5 [1] 7 [2] ve 1 [3] 5 [1] 7 [4] farklıdır Kesinlikle% 100 emin misiniz? Eğer öyleyse, o zaman daha uygun hale gelemezsiniz (tek bir iş parçacığında).
katma yazar Mooing Duck, kaynak
Örneğiniz (kod değil) kafa karıştırıcı
katma yazar KillianDS, kaynak

6 cevap

Aslında, değerlerin 1 ile 100 arasında olması çok önemlidir! Çünkü 1.000.000 büyüklüğündeki bir vektörde, eşit sayıda bir numaraya sahipsiniz ve hepsini kontrol etmeniz gerekmez! Yapabilecekleriniz aşağıdaki gibidir:

Not: aşağıdaki kod sadece bir taslaktır! Yeterli hata kontrolüne sahip olmayabilir ve sadece kopya yapıştırmak için değil, size fikir vermek için burada!

Not2: Cevabı yazdığımda, sayıların [0, 99] aralığında olduğunu varsaydım. Sonra onlar gerçekten [1, 100] içinde olduklarını okudum. Açıkçası bu bir problem değildir ve -1 sayısını ya da daha iyisini yapabilir, tüm 100'leri 101'lere dönüştürebilirsiniz.

bool exists[100] = {0}; //exists[i] means whether i exists in your vector

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
    exists[vect[i]] = true;

Sonra, daha önce yaptığınız şeye benziyorsunuz:

for(unsigned int x = 0; x < 98; x++)
  if (exists[x])
    for(unsigned int y = x+1; y < 99; y++)
      if (exists[y])
        for(unsigned int z = y+1; z < 100; z++)
          if (exists[z])
          {
           //{x, y, z} is an answer
          }

Yapabileceğiniz başka bir şey, çiftleri oluşturmaya daha az zaman ayırmaya hazırlanmak için daha fazla zaman harcamaktır. Örneğin:

int nums[100]; //from 0 to count are the numbers you have
int count = 0;

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
  bool exists = false;
  for (int j = 0; j < count; ++j)
    if (vect[i] == nums[j])
    {
      exists = true;
      break;
    }
  if (!exists)
    nums[count++] = vect[i];
}

Sonra

for(unsigned int x = 0; x < count-2; x++)
  for(unsigned int y = x+1; y < count-1; y++)
    for(unsigned int z = y+1; z < count; z++)
    {
     //{nums[x], nums[y], nums[z]} is an answer
    }

100'ün bir değişken olabileceğini düşünelim, bu yüzden k olarak adlandırın ve dizideki mevcut sayılar m olarak tanımlayın ( değerinden küçük veya ona eşittir) k ).

İlk yöntemde, oldukça hızlı olan değeri aramak için O (n) hazırlama ve O (m ^ 2 * k) işlemlerine sahipsiniz.

İkinci yöntemde, değerlerin oluşturulması için O (nm) hazırlama ve O (m ^ 3) kodunuz vardır. n ve m değerleriniz verildiğinde, hazırlık çok uzun sürüyor.

Her iki dünyanın en iyisini elde etmek için iki yöntemi birleştirebilirsiniz, bu yüzden böyle bir şey:

int nums[100];          //from 0 to count are the numbers you have
int count = 0;
bool exists[100] = {0}; //exists[i] means whether i exists in your vector

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
  if (!exists[vect[i]])
    nums[count++] = vect[i];
  exists[vect[i]] = true;
}

Sonra:

for(unsigned int x = 0; x < count-2; x++)
  for(unsigned int y = x+1; y < count-1; y++)
    for(unsigned int z = y+1; z < count; z++)
    {
     //{nums[x], nums[y], nums[z]} is an answer
    }

Bu yöntem, benzersiz üçüzün bulmak için O (n) hazırlık ve O (m ^ 3) maliyetine sahiptir.

Edit: It turned out that for the OP, the same number in different locations are considered different values. If that is really the case, Sonra I'm sorry, there is no faster solution. The reason is that all the possible combinations themselves are C(n, m) (That's a combination) that although you are generating each one of them in O(1), it is still too big for you.

4
katma
Umarım kodun herhangi bir yerinde aptalca bir hata yapmadım.
katma yazar Shahbaz, kaynak
Teşekkürler, fikrim var.
katma yazar Sinjuice, kaynak

Orada sahip olduğunuz ilmik gövdesini hızlandırmak için yapılabilecek hiçbir şey yok. 1M vektör boyutunda, bir trilyon döngü yinelemesi yaptığınızı düşünün.

Bunun gibi tüm kombinasyonları üretmek üstel bir problemdir, bu da girdi boyutu yeterince büyük olduğunda pratik olarak çözemeyeceğiniz anlamına gelir. Tek seçeneğiniz, mümkünse sorununuzu "çözmek" için uygulamanızın özel bilgisinden (sonuçlara neye ihtiyacınız olduğu ve tam olarak nasıl kullanılacağı) yararlanmak olacaktır.

2
katma
Evet şimdi görüyorum!
katma yazar Shahbaz, kaynak
Değerler 0 ile 100 arasındadır, bu yüzden onu gerçekten geliştirebilirsiniz
katma yazar Shahbaz, kaynak
Bu 3 değerin geçerli bir üçgen yapıp yapamayacağını kontrol etmek için kullanılacaktır.
katma yazar Sinjuice, kaynak
@ Payn3: yani 1 [0] 5 [1] 7 [2] ve 1 [3] 5 [1] 7 [4] aslında farklı mı değil mi? Öyle dedin, ama sadece üçgenleri kontrol ediyorsan, o zaman farklı olmazlardı.
katma yazar Mooing Duck, kaynak
@ Payn3: Ve bu üçgene ihtiyacınız var ... Buraya cevap verme, bu tür bir analiz yapmak için bir yorumda yeterli bilgiyi sağlayamamanın bir yolu yoktur.
katma yazar Jon, kaynak

Possibly you can sort your input, make it unique, and pick x[a], x[b] and x[c] when a < b < c. The sort will be O(n log n) and picking the combination will be O(n³). Still you will have less triplets to iterate over:

std::vector x = original_vector;
std::sort(x.begin(), x.end());
std::erase(std::unique(x.begin(), x.end()), x.end());
for(a = 0; a < x.size() - 2; ++a)
  for(b=a+1; b < x.size() - 1; ++b)
     for(c=b+1; c< x.size(); ++c
        issue triplet(x[a],x[b],x[c]);
0
katma

Gerçek verilerinize bağlı olarak, önce her değerle en fazla üç girişe sahip olan bir vektör oluşturup bunun yerine yinelemek suretiyle önemli ölçüde hızlandırabilirsiniz.

0
katma
Bunun çok fazla bellek alacağını düşünüyorum ve bunu üretmek şu an sahip olduğu kadar hızlı.
katma yazar Mooing Duck, kaynak
Bir şey değil. Benim önerdiğim şey, esas olarak shahbazın üstündekiyle tamamen aynı.
katma yazar 500 - Internal Server Error, kaynak

R15habh'ın işaret ettiği gibi, dizideki değerlerin aslında 1-100 olduğu aslında önemli olduğunu düşünüyorum.

İşte yapabilecekleriniz: diziden bir geçiş yapmak, değerleri benzersiz bir kümeye okumak. Bu kendi başına O (n) zaman karmaşıklığıdır. Set, O (1) uzay karmaşıklığı anlamına gelen 100'den fazla öğeye sahip olmayacaktır.

Artık 3 maddelik tüm permütasyonları oluşturmaya ihtiyaç duyduğunuzdan, yine de 3 iç içe döngülere ihtiyacınız olacak, ancak potansiyel olarak çok büyük bir dizi üzerinde çalışmak yerine en fazla 100 öğeye sahip bir set üzerinde çalışacaksınız.

Overall time complexity depends on your original data set. For a small data set, time complexity will be O(n^3). For a large data set, it will approach O(n).

0
katma
Diyor ki: 1 [0] 5 [1] 7 [2] ve 1 [3] 5 [1] 7 [4] birbirinden farklı , böylece yinelenen değerleri kaldıramazsınız.
katma yazar Mooing Duck, kaynak

If understand your application correctly then you can use a tuple instead, and store in either a set or hash table depending on your requirements. If the normal of the tri matters, then make sure that you shift the tri so that lets say the largest element is first, if normal shouldn't matter, then just sort the tuple. A version using boost & integers:

#include 
#include 
#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"

int main()
{
    typedef boost::tuple< int, int, int > Tri;
    typedef std::set< Tri > TriSet;
    TriSet storage;
   //1 duplicate
    int exampleData[4][3] = { { 1, 2, 3 }, { 2, 3, 6 }, { 5, 3, 2 }, { 2, 1, 3 } };
    for( unsigned int i = 0; i < sizeof( exampleData )/sizeof( exampleData[0] ); ++i )    
    {
        std::sort( exampleData[i], exampleData[i] + ( sizeof( exampleData[i] )/sizeof( exampleData[i][0] ) ) );
        if( !storage.insert( boost::make_tuple( exampleData[i][0], exampleData[i][1], exampleData[i][2] ) ).second )
            std::cout << "Duplicate!" << std::endl;
        else
            std::cout << "Not duplicate!" << std::endl;
    }
}
0
katma
Sorununu yanlış anladım gibi görünüyor, değil mi?
katma yazar Ylisar, kaynak