Алгоритм генерации комбинаций списков с элементами для каждого индекса, поменяемого местами - PullRequest
Новая
       10

Алгоритм генерации комбинаций списков с элементами для каждого индекса, поменяемого местами

0 голосов
/ 06 февраля 2019

У меня есть два списка с N элементами в каждом.

Let N = 9: 

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

Давайте поменяем первый элемент каждого списка.Существует две возможности: 

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

[a2, b1, c1, d1, e1, f1, g1, h1, i1]
[a1, b2, c2, d2, e2, f2, g2, h2, i2]

Для каждой возможности давайте поменяем второй элемент каждого списка.Существует четыре варианта: 

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

[a2, b1, c1, d1, e1, f1, g1, h1, i1]
[a1, b2, c2, d2, e2, f2, g2, h2, i2]

[a1, b2, c1, d1, e1, f1, g1, h1, i1]
[a2, b1, c2, d2, e2, f2, g2, h2, i2]

[a2, b2, c1, d1, e1, f1, g1, h1, i1]
[a1, b1, c2, d2, e2, f2, g2, h2, i2]

и т. Д.

Какие самые быстрые алгоритмы для генерации всех комбинаций для 2 списков и для M списков?
Как называетсяэтого конкретного процесса?
Какое общее число комбинаций дано M, N?

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

Поскольку для каждой позиции вновь сформированного списка L1 элемент может быть выбран из первого или второго списка, для каждой позиции есть два варианта.Соответствующий второй список L2 будет сформирован путем выбора элементов, которые не были выбраны, и это можно сделать только одним способом.Таким образом, существуют 2^N комбинации, где N - длина исходных списков.

Используя это мышление, легко написать генератор, используя 2^N двоичные маски - для каждой i из *От 1007 * до 2^N - 1 мы сформируем список, определяемый двоичным представлением этого числа.Вот код Python: 

a = ['a1', 'b1', 'c1']
b = ['a2', 'b2', 'c2']
for i in range(2 ** len(a)):
  l1, l2 = [], []
  mask = i
  for j in range(len(a)):
    l1.append(a[j] if mask % 2 == 0 else b[j])
    l2.append(b[j] if mask % 2 == 0 else a[j])
    mask /= 2
  print(l1, l2)

печатает 

(['a1', 'b1', 'c1'], ['a2', 'b2', 'c2'])
(['a2', 'b1', 'c1'], ['a1', 'b2', 'c2'])
(['a1', 'b2', 'c1'], ['a2', 'b1', 'c2'])
(['a2', 'b2', 'c1'], ['a1', 'b1', 'c2'])
(['a1', 'b1', 'c2'], ['a2', 'b2', 'c1'])
(['a2', 'b1', 'c2'], ['a1', 'b2', 'c1'])
(['a1', 'b2', 'c2'], ['a2', 'b1', 'c1'])
(['a2', 'b2', 'c2'], ['a1', 'b1', 'c1'])

Поскольку выходной размер равен O(N * 2^N), вы не можете создать алгоритм с большей сложностью, чем этот.

0 голосов
/ 06 февраля 2019

Если я правильно читаю, вы можете использовать что-то вроде этого (написано в JS): 

const arrayA = ['a1', 'b1', 'c1', 'd1', 'e1', 'f1', 'g1', 'h1', 'i1']
const arrayB = ['a2', 'b2', 'c2', 'd2', 'e2', 'f2', 'g2', 'h2', 'i2']
let results = [{a: arrayA, b: arrayB}]

for (let i = 0; i < arrayA.length; i++) {

    let newResults = []

    for (let j = 0; j < results.length; j++) {
        let result = results[j]

        // Copy the arrays
        let outA = result.a.slice()
        let outB = result.b.slice()

        // Get the items to switch
        let itemA = outA[i]
        let itemB = outB[i]

        // Switch positions in the new arrays
        outA[i] = itemB
        outB[i] = itemA

        // Append the new item to the results
        newResults.push({a: outA, b: outB})

    }

    results = results.concat(newResults)

}

console.log(results.length)

Конечное число будет 2 ^ N, в данном случае 512

...