Все возможные комбинации.Быстрее

Question

У меня есть вектор чисел от 1 до 100 (это не важно), который может принимать значения от 3 до 1.000.000 значений.

Если кто-нибудь может помочь мне получить 3 уникальные комбинации * значений из этого вектора.

* Уникальный

Пример: в массиве есть следующие значения: 1 [0] 5 [1] 7 [2] 8 [3] 7 [4] (индекс [x])

В этом случае 1 [0] 5 [1] 7 [2] и 1 [3] 5 [1] 7 [4] различны, но 1 [0] 5 [1] 7 [2] и 7 [ 2] 1 [0] 5 [1] одинаковы (дубликаты)

Мой алгоритм немного медленный, когда я работаю с большим количеством значений (пример 1.000.000). Так что я хочу, чтобы это был более быстрый способ.

           for(unsigned int x = 0;x<vect.size()-2;x++){
                for(unsigned int y = x+1;y<vect.size()-1;y++){
                    for(unsigned int z = y+1;z<vect.size();z++)
                    {

                        // do thing with vect[x],vect[y],vect[z]
                    }
                }
            }

Answer 1

На самом деле очень важно, чтобы ваши значения были от 1 до 100!Потому что с вектором размером 1,000,000 у вас много одинаковых чисел, и вам не нужно проверять их все!Что вы можете сделать, это следующее:

Примечание: следующий код является лишь наброском!В ней может отсутствовать достаточная проверка ошибок, и она здесь, чтобы дать вам идею, а не для вставки копии!

Примечание 2: Когда я писал ответ, я предполагал, что числа находятся в диапазоне [0, 99].Затем я прочитал, что они на самом деле в [1, 100].Очевидно, что это не проблема, и вы можете либо -1 на все числа, либо даже лучше, изменить все 100 на 101.

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;

Затем вы делаете то же, что делали раньше:

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
          }

Еще одна вещь, которую вы можете сделать, это потратить больше времени на подготовку, чтобы меньше времени создавать пары.Например:

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

Тогда

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, поэтому назовем ее k, а фактические числа, представленные в массиве, будут m (который меньше или равен k).

При первом способе у вас есть O(n) подготовка и O(m^2*k) операции для поиска достаточно быстрого значения.

Во втором методе у вас есть O(nm) подготовка и O(m^3) для генерации значений.Учитывая ваши значения для n и m, подготовка занимает слишком много времени.

Вы могли бы фактически объединить два метода, чтобы получить лучшее из обоих миров, что-то вроде этого:

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

Тогда:

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
    }

Этот метод имеет O(n) подготовку и O(m^3) стоимость для поиска уникальных триплетов.

Редактировать: Оказалось, чтодля OP одно и то же число в разных местах считается разными значениями.Если это действительно так, то извините, более быстрого решения нет.Причина в том, что все возможные комбинации C(n, m) (это комбинация ), что, хотя вы генерируете каждую из них в O(1), она все еще слишком велика для вас.

Answer 2

Нет ничего, что можно сделать для ускорения имеющегося у вас тела цикла. Учтите, что с размером вектора 1M вы делаете один триллион итераций цикла.

Создание всех подобных комбинаций является экспоненциальной проблемой, что означает, что вы не сможете практически решить ее, когда размер ввода станет достаточно большим. Единственным вариантом будет использование определенных знаний о вашем приложении (для чего вам нужны результаты и как именно они будут использоваться), чтобы «обойти» проблему, если это возможно.

Answer 3

Если вы правильно понимаете свое приложение, вы можете вместо этого использовать кортеж и хранить его в виде набора или хеш-таблицы в зависимости от ваших требований.Если нормаль tri имеет значение, то убедитесь, что вы смещаете tri так, чтобы, скажем, самый большой элемент был первым, если normal не должен иметь значения, тогда просто сортируйте кортеж.Версия с использованием буста и целых чисел:

#include <set>
#include <algorithm>
#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;
    }
}

Answer 4

Как указал r15habh, я думаю, что факт, что значения в массиве находятся в диапазоне 1-100 , на самом деле важен.

Вот что вы можете сделать: сделать один проход через массив, считывая значения в уникальный набор. Это само по себе является O (n) сложностью времени. Набор будет содержать не более 100 элементов, что означает O (1) сложность пространства.

Теперь, поскольку вам нужно сгенерировать все перестановки из 3 элементов, вам все равно понадобятся 3 вложенных цикла, но вместо работы с потенциально огромным массивом вы будете работать с набором, содержащим не более 100 элементов. 1009 *

Общая сложность времени зависит от вашего исходного набора данных. Для небольшого набора данных сложность времени будет O (n ^ 3). Для большого набора данных он приблизится к O (n).

Answer 5

В зависимости от ваших фактических данных, вы можете значительно ускорить их, сначала создав вектор, содержащий не более трех записей с каждым значением, и переберите его.

Answer 6

Возможно, вы можете отсортировать ввод, сделать его уникальным и выбрать x [a], x [b] и x [c], когда a < b < c.Сортировка будет O (n log n), а выбор комбинации будет O (n³).Тем не менее, у вас будет меньше триплетов для перебора:

std::vector<int> 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]);