Как найти все перестановки, состоящие из 1 элемента, из переменного числа массивов переменной длины?

Question

У меня есть массив U массивов D, которые различаются по длине. Мне нужно иметь возможность возвращать все перестановки индексов массива, которые бы выбирали разные перестановки, состоящие из 1 элемента из каждого набора. Мне также требуется, чтобы этот алоритм был представлен как объект, который запоминает только последнюю перестановку и возвращает следующую перестановку с помощью метода get_next.

Например, U = [array_of_size_n1, array_of_size_n2, array_of_size_n3] Было бы n1*n2*n3 перестановок, каждая 3 элементов длиной.

Редактировать: количество наборов также варьируется.

Answer 1

Если вы используете python, это часть стандартной библиотеки: itertools.product. Но при условии, что это не так, вот версия с псевдокодом.

// Create an initialised array of indexes.
int[] index0(arrays) {
    // We require all arrays to be non-empty.
    for a in arrays {
        assert len(a) != 0;
    }
    return new int[len(arrays)];
}

// Increment the indices. Returns false when the indices wrap round to the start.
bool next_index(indices, arrays) {
    for (i = len(indices) - 1; i >= 0; --i) {
        indices[i] += 1
        if indices[i] < len(arrays[i]) {
            return true;
        }
        indices[i] = 0;
    }
    return false;
}

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

indices = index0(arrays); 
{
    for (i = 0; i < len(arrays); ++i) {
        print arrays[i][indices[i]];
    }
    print
} while next_index(indices);

Answer 2

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

if (pos3 == array_of_size_n3 -1)
{
   if (pos2 == size_of_array_2 -1)
   {
       pos1 = (pos1 + 1) % size_of_array_1

   }
   pos2 = (pos2 + 1) % size_of_array_2
}
pos3 = (pos3 + 1) % size_of_array_3

print array1[pos1], array2[pos2], array3[pos3]

РЕДАКТИРОВАТЬ: В случае, если количество массивов меняется, держать ваши переменные позиции в массиве. На самом деле это, вероятно, было бы лучше в любом случае. Таким образом, вы можете ссылаться на переменную pos точно так же, как и на сам массив.

Answer 3

Чтобы придерживаться того, что сказал Анон, вы не просто зацикливаетесь на них.Вы поддерживаете состояние в своем классе, чтобы знать, каким был ваш последний индекс для каждого массива.Логика та же, но вы не работаете в непрерывном цикле.Логика псевдокода будет:

get_next()
{
  oldn3 = this.n3;
  oldn2 = this.n2;
  oldn1 = this.n1;

  if(this.n3 == this.a3.Count)
     this.n3 = 0;
  else
     this.n3++;

  if(oldn3 > this.n3)
    if(this.n2 == this.a2.Count)
      this.n2 = 0;
    else
      this.n2++;

  if(oldn2 > this.n2)
    if(this.n1 == this.a1.Count)
      this.n1 = 0;
    else
      this.n1++;

  if(oldn1 > this.n1)
    return NO_MORE_PERMS;

  return [n1,n2,n3];  
}

getCurrent()
{
  return [n1,n2,n3];
}

Answer 4

Так ... что насчет этого не просто?

Вы хотите итератор. Вы хотите, чтобы он перебрал последний массив. Когда он доберется до конца этого массива, увеличьте его текущую позицию во втором по величине массиве и вернитесь к началу последнего массива.

psuedocode с использованием синтаксиса C # s yield return:

foreach n1 in a1
    foreach n2 in a2
        foreach n3 in a3
            yield return (n1, n2, n3)

РЕДАКТИРОВАТЬ: Если количество наборов варьируется, вы можете использовать некоторую форму рекурсии:

function next(list)
    firstArray = list.first
    iterator = iterator(list.rest)
    if !iterator
        foreach i in firstArray
            yield return i
    else
        foreach i in firstArray
            while (iterator.hasNext)
                yield return (i, iterator.next)

Рассмотрим поведение при передаче списка длины 1, затем рассмотрим поведение списка длины 2 и убедитесь, что оно действительно работает.