Alle mogelijke combinatie. Snellere manier

Ik heb een vector met getallen tussen 1 en 100 (dit is niet belangrijk) die tussen 3 en 1.000.000 waarden kan aannemen.

Als iemand me kan helpen om 3 unieke unieke * -combinaties van die vector te krijgen.

*Uniek

Voorbeeld: ik heb in de array de volgende waarden: 1 [0] 5 [1] 7 [2] 8 [3] 7 [4] (de [x] is de index)

In dit geval zijn 1 [0] 5 [1] 7 [2] en 1 [3] 5 [1] 7 [4] verschillend, maar 1 [0] 5 [1] 7 [2] en 7 [2] 1 [0] 5 [1] zijn hetzelfde (duplicaat)

Mijn algoritme is een beetje traag als ik met heel veel waarden werk (bijvoorbeeld 1.000.000). Dus wat ik wil is een snellere manier om het te doen.

           for(unsigned int x = 0;x
 1
toegevoegd bewerkt
Bekeken: 5
de bron
1.000.000 waarden hebben 1.000.000 * 999.999 * 999.998/6 unieke combinaties. Zelfs als je elk van deze combinaties direct krijgt, zou het bekijken ervan voor altijd duren!
toegevoegd de auteur Shahbaz, de bron
Heeft index [3] niet waarde 8 in dit voorbeeld?
toegevoegd de auteur Shahbaz, de bron
Is het uw doel om elke mogelijke combinatie van waarden te krijgen? Als je 10 ^ 9-waarden hebt, krijg je 10 ^ 27/3 combinaties om te testen. Doen "denken" dat vele malen duur kan zijn ...
toegevoegd de auteur Brian, de bron
Weet je zeker dat de woning tussen de 1-100 niet belangrijk is?
toegevoegd de auteur r15habh, de bron
1 [0] 5 [1] 7 [2] en 1 [3] 5 [1] 7 [4] are differenter Bent u absoluut 100% zeker van dat? Als dat zo is, kun je niet meer optimaal worden (in een enkele thread).
toegevoegd de auteur Mooing Duck, de bron
Uw voorbeeld (niet de code) is verwarrend
toegevoegd de auteur KillianDS, de bron

6 antwoord

Het is zelfs heel belangrijk dat uw waarden tussen 1 en 100 liggen! Omdat je met een vector van 1.000.000 veel getallen hebt die gelijk zijn en je ze niet allemaal hoeft te inspecteren! Wat je kunt doen is het volgende:

Opmerking: de volgende code is slechts een overzicht! Het kan onvoldoende foutcontrole bevatten en is hier alleen om u het idee te geven, niet voor copy paste!

Opmerking 2: Toen ik het antwoord schreef, nam ik aan dat de getallen binnen het bereik [0, 99] lagen. Toen las ik dat ze daadwerkelijk in [1, 100] zijn. Dit is duidelijk geen probleem en je kunt ofwel -1 alle cijfers of zelfs beter, alle 100s naar 101s veranderen.

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;

Dan doe je hetzelfde als wat je eerder deed:

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
          }

Een ander ding dat je kunt doen is meer tijd besteden aan voorbereiding om minder tijd te hebben om de paren te genereren. Bijvoorbeeld:

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

Dan

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
    }

Laten we 100 beschouwen als een variabele, dus laten we het k noemen, en de werkelijke aantallen die in de array aanwezig zijn als m (die kleiner is dan of gelijk is aan k ).

Met de eerste methode hebt u O (n) voorbereiding en O (m ^ 2 * k) handelingen om te zoeken naar de waarde die vrij snel is.

In de tweede methode hebt u O (nm) voorbereiding en O (m ^ 3) voor het genereren van de waarden. Gegeven uw waarden voor n en m duurt de voorbereiding te lang.

Je zou eigenlijk de twee methoden kunnen samenvoegen om het beste van beide werelden te krijgen, dus zoiets als dit:

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

Dan:

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
    }

Deze methode heeft O (n) voorbereiding en O (m ^ 3) kosten om de unieke tripletten te vinden.

Edit: It turned out that for the OP, the same number in different locations are considered different values. If that is really the case, Dan 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
toegevoegd
de bron
Ik hoop dat ik nergens in de code een domme fout heb gemaakt.
toegevoegd de auteur Shahbaz, de bron
Bedankt, ik heb het idee.
toegevoegd de auteur Sinjuice, de bron

Er is echt niets dat kan worden gedaan om het luslichaam dat je daar hebt te versnellen. Bedenk dat met 1M vectorgrootte, u één biljoen lus-iteraties maakt.

Het produceren van alle dergelijke combinaties is een exponentieel probleem, wat betekent dat je het niet praktisch kunt oplossen wanneer de ingangsgrootte groot genoeg wordt. Uw enige optie zou zijn om gebruik te maken van specifieke kennis van uw toepassing (waarvoor u de resultaten nodig heeft en hoe ze precies zullen worden gebruikt) om het probleem zo mogelijk te 'omzeilen'.

2
toegevoegd
de bron
Ja, ik zie het nu!
toegevoegd de auteur Shahbaz, de bron
De waarden liggen tussen 0 en 100, dus je kunt het echt veel verbeteren
toegevoegd de auteur Shahbaz, de bron
Het zal worden gebruikt om te controleren of die 3 waarden een geldige driehoek kunnen vormen. (Een eenvoudige als)
toegevoegd de auteur Sinjuice, de bron
@ Payn3: dus de zijn 1 [0] 5 [1] 7 [2] en 1 [3] 5 [1] 7 [4] eigenlijk anders of niet? U zei dat ze dat waren, maar als u alleen driehoeken controleert, dan zouden ze niet anders zijn.
toegevoegd de auteur Mooing Duck, de bron
@ Payn3: En je hebt die driehoek nodig om ...? Geef hier geen antwoord, je kunt op geen enkele manier genoeg informatie in een opmerking plaatsen om dit soort analyse te doen.
toegevoegd de auteur Jon, de bron

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
toegevoegd
de bron

Afhankelijk van uw werkelijke gegevens kunt u het mogelijk aanzienlijk versnellen door eerst een vector te maken met ten hoogste drie vermeldingen voor elke waarde en in plaats daarvan een andere te herhalen.

0
toegevoegd
de bron
Ik denk dat dat veel geheugen in beslag zou nemen, en het genereren ervan is precies zo snel als wat hij nu heeft.
toegevoegd de auteur Mooing Duck, de bron
Helemaal niet. Wat ik suggereerde is in essentie precies hetzelfde als wat shahbaz hierboven heeft.
toegevoegd de auteur 500 - Internal Server Error, de bron

Zoals r15habh aangaf, vind ik het feit dat de waarden in de array tussen de -1-100 zijn in feite belangrijk.

Dit is wat u kunt doen: maak een doorloop door de array en lees waarden in een unieke set. Deze alleen is O (n) tijdcomplexiteit. De set heeft niet meer dan 100 elementen, wat O (1) ruimtecomplexiteit betekent.

Omdat je nu alle permutaties van 3 items moet genereren, heb je nog steeds 3 geneste lussen nodig, maar in plaats van dat je werkt op de mogelijk enorme array, zul je werken op een set die maximaal 100 elementen bevat.

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
toegevoegd
de bron
Hij zegt: 1 [0] 5 [1] 7 [2] en 1 [3] 5 [1] 7 [4] zijn verschillend , dus je kunt geen dubbele waarden verwijderen.
toegevoegd de auteur Mooing Duck, de bron

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
toegevoegd
de bron
Het lijkt erop dat ik je probleem verkeerd heb begrepen, doh.
toegevoegd de auteur Ylisar, de bron