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

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

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

Изменить: количество наборов также меняется.

Ответы

Ответ 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);

Ответ 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]

EDIT: в случае, когда количество массивов меняется, удерживайте переменные позиции в массиве. На самом деле, вероятно, было бы лучше в любом случае. Таким образом, вы можете ссылаться на переменную pos так же, как вы ссылаетесь на сам массив.

Ответ 3

Итак... что об этом не просто?

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

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

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

EDIT: если количество наборов меняется, вы можете использовать некоторую форму рекурсии:

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 и убедитесь, что оно действительно работает.

Ответ 4

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

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