Как мне найти набор уникальных пар массива?

Question

Предположим, у меня есть следующий массив:

array = [0, 1, 2, ... , n]

Как мне найти такой набор, чтобы все пары в наборе были уникальными и неповторяющимися элементами?

Это значитчто:

• (x, y) = (y, x), поэтому, если (x, y) находится в наборе, то (y, x) не будет и наоборот

• Если элемент уже используется, его нельзя использовать снова.

Например: если (1,2) в наборе, то в наборе не может быть пары с 1 или 2.

Контекст: я создаю игру памяти, котораяРазмещает монеты на доске из 2n элементов.Я хочу, чтобы каждая итерация игры размещала элементы в случайных местах на доске.

Например:

Suppose I have: [A, B, C, D, E, F]
Since [A, B, C, D, E, F] is length 6, then the board will consist of 12 elements.
My board will look like the following such that the elements were randomly placed:

A B C D

C A F B

E F E D

Честно говоря, я не знаю, как решить эту проблему без использования метода грубой силы O (n ^ 2).Я полагаю, что может быть другой алгоритм, который будет более эффективным.

Answer 1

Вы можете использовать перемешивание Фишера-Йейтса , чтобы эффективно перемешать массив с двумя значениями каждой монеты за время O (n).Алгоритм в основном берет отсортированный список и продолжает обменивать два случайных элемента из списка до тех пор, пока список не будет математически перемешан / случайным образом.

В JavaScript:

// Generate seed array.
// Numbers are used here for simplicity, but the array can contain any type like String.
a = [];
for (i=0; i<4; i++) { a.push(i, i); }
console.log(a);  // [0, 0, 1, 1, 2, 2, 3, 3]

// This is the "modern version" pseudo-code ported to JavaScript:
// To shuffle an array a of n elements (indices 0..n-1):
n = a.length;
// for i from n−1 downto 1 do
for (i=n-1; i>0; i--)  {  
  // j ← random integer such that 0 ≤ j ≤ i
  j = Math.floor(Math.random() * (i + 1));

  // exchange a[j] and a[i] 
  tmp = a[j];
  a[j] = a[i];
  a[i] = tmp;
}
console.log(a);  // [2, 1, 3, 3, 0, 1, 0, 2]

Примечание: Несмотря на то, что O (n ^ 2) в вашем алгоритме звучит плохо, это, вероятно, не имеет большого значения для перемешивания элементов вашей игры с монетами.В начале вы тасуете только небольшое количество предметов.Таким образом, вы, вероятно, не сможете определить, является ли сложность O (n) или O (n ^ 2).Сложность становится важной только тогда, когда n становится действительно большим, или вам нужно постоянно повторять вычисления (например, миллионы раз в секунду).Сначала я предлагаю оптимизировать ваш код для удобства чтения.Тогда оптимизируйте только тогда, когда это явно необходимо.

Answer 2

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

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