Эффективно вычислять векторные комбинации

Question

Я работаю над исследовательской проблемой из любопытства и не знаю, как запрограммировать логику, которую я имею в виду.Позвольте мне объяснить это вам:

У меня есть четыре вектора, скажем, например,

v1 = 1 1 1 1
v2 = 2 2 2 2
v3 = 3 3 3 3
v4 = 4 4 4 4

Теперь я хочу добавить их по комбинации, то есть

v12 = v1+v2
v13 = v1+v3
v14 = v1+v4
v23 = v2+v3
v24 = v2+v4
v34 = v3+v4

До этого шага все нормально.Проблема в том, что теперь я хочу добавить каждый из этих векторов по одному вектору из v1, v2, v3, v4, который он не добавил ранее.Например:

v3 и v4 не были добавлены в v12, поэтому я хочу создать v123 и v124.Аналогично для всех векторов, таких как

v12 should become:
v123 = v12+v3
v124 = v12+v4

v13 should become:
v132 // This should not occur because I already have v123
v134

v14 should become:
v142 // Cannot occur because I've v124 already
v143 // Cannot occur

v23 should become:
v231 // Cannot occur
v234 ... and so on.

Важно, чтобы я не делал все сразу за один шаг в начале.Как, например, я могу сделать (4 выбрать 3) 4C3 и завершить его, но я хочу сделать это шаг за шагом на каждой итерации.

Как мне это запрограммировать?

PS: я пытаюсь работать над модифицированной версией алгоритма apriori для интеллектуального анализа данных.

Answer 1

В C ++, учитывая следующую процедуру:

template <typename Iterator>
inline bool next_combination(const Iterator first,
                                   Iterator k,
                             const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         std::iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         std::rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         std::rotate(k,itr2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Затем вы можете перейти к следующему:

int main()
{
   unsigned int vec_idx[] = {0,1,2,3,4};

   const std::size_t vec_idx_size = sizeof(vec_idx) / sizeof(unsigned int);

   {
      // All unique combinations of two vectors, for example, 5C2
      std::size_t k = 2;
      do
      {
         std::cout << "Vector Indicies: ";
         for (std::size_t i = 0; i < k; ++i)
         {
           std::cout << vec_idx[i] << " ";
         }
      }
      while (next_combination(vec_idx,
                              vec_idx + k,
                              vec_idx + vec_idx_size));
   }

   std::sort(vec_idx,vec_idx + vec_idx_size);

   {
      // All unique combinations of three vectors, for example, 5C3
      std::size_t k = 3;
      do
      {
         std::cout << "Vector Indicies: ";
         for (std::size_t i = 0; i < k; ++i)
         {
           std::cout << vec_idx[i] << " ";
         }
      }
      while (next_combination(vec_idx,
                              vec_idx + k,
                              vec_idx + vec_idx_size));
   }

   return 0;
}

** Примечание 1: * Из-за интерфейса, ориентированного на итератордля подпрограммы next_combination можно также использовать любой контейнер STL , который поддерживает прямую итерацию через итераторы, например std::vector, std::deque и std::list, чтобы назвать несколько.

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

Answer 2

Я думаю, что эту проблему можно решить, отметив, какая комбинация произошла.

Моя первая мысль: вы можете использовать 3-мерный массив, чтобы отметить, какая комбинация произошла. Но это не очень хорошо.

Как насчет битового массива (такого как целое число) для пометки? Такие как:

Num 1 = 2^0 for vector 1
Num 2 = 2^1 for vector 2
Num 4 = 2^2 for vector 3
Num 8 = 2^3 for vector 4

Когда вы делаете композицию, просто добавьте все репрезентативные номера. Например, вектор 124 будет иметь значение: 1 + 2 + 8 = 11. Это значение уникально для каждой комбинации.

Это только моя мысль. Надеюсь, это вам как-нибудь поможет.

РЕДАКТИРОВАТЬ : Может быть, я не достаточно ясно о моей идее. Я попытаюсь объяснить это немного яснее:

1) Назначьте для каждого вектора репрезентативное число. Этот номер является идентификатором вектора, и он уникален. Кроме того, сумма каждого подмножества этих чисел является уникальной, это означает, что если у нас есть сумма k представительного числа является М; мы можем легко узнать, какие векторы принимают участие в сумме.

Мы делаем это по присваиванию: 2 ^ 0 для вектора 1; 2 ^ 1 для вектора 2; 2 ^ 2 для вектора 3 и т. Д. ...

С каждой M = суммой (2 ^ x + 2 ^ y + 2 ^ z + ...) = (2 ^ x ИЛИ 2 ^ y ИЛИ 2 ^ z ИЛИ ...). Мы знаем, что вектор (x + 1), (y + 1), (z +1) ... принимают участие в сумме. Это легко проверить с помощью экспресс-числа в двоичном режиме.

Например, мы знаем, что:

2 ^ 0 = 1 (двоичный) 2 ^ 1 = 10 (двоичный) 2 ^ 2 = 100 (двоичный) ...

Так что, если у нас есть сумма 10010 (двоичная), мы знаем, что вектор (число: 10) и вектор (число: 10000) объединяются в сумму.

И, что лучше, сумма здесь может быть вычислена оператором «ИЛИ», что также легко понять, если вы выразите число в двоичном виде.

2) Используя приведенные выше факты, каждый раз, прежде чем подсчитать сумму вашего вектора, вы можете сначала добавить / ИЛИ их представительный номер. И вы можете отслеживать их в виде массива поиска. Если сумма уже существует в массиве поиска, вы можете опустить ее. Тем самым вы можете решить проблему.

Answer 3

Может быть, я неправильно понимаю, но разве это не эквивалентно генерации всех подмножеств (набор мощности) 1, 2, 3, 4, а затем для каждого элемента набора мощности, суммируя вектор?Например:

//This is pseudo C++ since I'm too lazy to type everything
//push back the vectors or pointers to vectors, etc.
vector< vector< int > > v = v1..v4;

//Populate a vector with 1 to 4
vector< int > n = 1..4

//Function that generates the power set {nil, 1, (1,2), (1,3), (1,4), (1,2,3), etc.
vector< vector < int > > power_vec = generate_power_set(n);

//One might want to make a string key by doing a Perl-style join of the subset together by a comma or something...
map< vector < int >,vector< int > > results;
//For each subset, we sum the original vectors together
for subset_iter over power_vec{
    vector<int> result;
    //Assumes all the vecors same length, can be modified carefully if not.
    result.reserve(length(v1));
    for ii=0 to length(v1){
        for iter over subset from subset_iter{
            result[ii]+=v[iter][ii];
        }
    }
    results[*subset_iter] = result;
}

Если эту идею вы имели в виду, вам все еще нужна функция набора мощности, но этот код легко найти, если вы ищете набор мощности.Например, Получение powerset набора в Java .

Answer 4

1. Ведение списка всех для выбора двух значений.
2. Создание вектора наборов таким образом, чтобы набор состоял из элементов исходного вектора с элементами 4C2.Выполните итерацию по исходным векторам и для каждого добавьте / создайте набор с элементами из шага 1. Сохраните вектор наборов, и только если набор отсутствует, добавьте результат к вектору.вектор множеств, полученный на шаге 2.

Но, как вы указали, самый простой - 4C3.

Вот что-то написанное на Python.Вы можете принять его в C ++

import itertools

l1 = ['v1','v2','v3','v4']
res = []
for e in itertools.combinations(l1,2):
    res.append(e)

fin = []
for e in res:
    for l in l1:
        aset = set((e[0],e[1],l))
        if aset not in fin and len(aset) == 3:
            fin.append(aset)
print fin

Это приведет к:

[set(['v1', 'v2', 'v3']), set(['v1', 'v2', 'v4']), set(['v1', 'v3', 'v4']), set(['v2', 'v3', 'v4'])]

Это тот же результат, что и 4C3.