-1

Suppose that I have the following array:

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

How do I find a set such that the pairs in the set are all unique and non-repeated elements?

This means that:

• (x, y) = (y, x) so if (x, y) is in the set, then (y, x) would not be & vice-versa

• If an element is already used, it cannot be used again.

E.g: if (1,2) is in the set, then there cannot be a pair in the set that has 1 or 2.

Context: I'm creating a memory game that places coins on a board of 2n elements. I want each iteration of the game to place the elements in random spaces on the board.

E.g: 

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

I frankly don't know how to solve this without doing an O(n^2) brute force method. I figure there might be another algorithm that would be more efficient.

Try Khov
  • 87
  • 1
  • 8
  • 3
    Share your code to show an attempt was made, – Sagar Agrawal Feb 24 '19 at 02:32
  • @SagarAgrawal the idea is that i don't know where to start and i'm not looking for a full algorithm but rather an idea of where to start or if it's even possible – Try Khov Feb 24 '19 at 02:39
  • Your sample input says ABCD but output has EF. Where has EF came from? – Sagar Agrawal Feb 24 '19 at 02:41
  • @SagarAgrawal sorry i forgot, i just fixed it thanks for the catch – Try Khov Feb 24 '19 at 02:44
  • 1
    If you’re creating memory game you can simply create two input arrays. Randomly evict elements from the array and place them randomly in 3 output arrays. – Sagar Agrawal Feb 24 '19 at 02:50
  • 2
    Create [A, A, B, B, C, C, D, D, E, E, F, F] and shuffle? – Ry- Feb 24 '19 at 02:51
  • @SagarAgrawal (Ry) omg I didn't realize it was simpler than I thought Okay so I take it that I create two arrays, one empty and the other one with the [A, A, B, B, ..., F, F] and then randomly insert them into the empty array and there I go I think I got it, thanks! – Try Khov Feb 24 '19 at 02:54
  • 1
    @TryKhov: No problem :) Note that you can do the shuffle in place, so only one array. – Ry- Feb 24 '19 at 02:59
  • See [Random number, which is not equal to the previous number](https://stackoverflow.com/q/40056297/); [run for random numbers and keep state \[duplicate\]](https://stackoverflow.com/q/41001101/) – guest271314 Feb 24 '19 at 03:01

2 Answers2

1

You can use the Fisher–Yates shuffle to efficiently shuffle an array with two of each coin value in O(n) time. The algorithom basically takes a sorted list, and keeps swapping two random elements from the list until the list is mathematically shuffled/random.

In 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]

Side note: Even though O(n^2) in your algorithm sounds bad, it probably doesn't make much difference for shuffling the items of your coin game. You only shuffle a small number of items once at the beginning. So you probably wouldn't be able to tell if the complexity is O(n) or O(n^2). Complexity only becomes important as that n becomes really big, or you need to continuously repeat the calculation (like millions of times per second). I suggest optimizing your code for readability, first. Then only optimize when it is obviously needed.

Leftium
  • 16,497
  • 6
  • 64
  • 99
  • Important to declare your variables in JavaScript. – Ry- Feb 24 '19 at 04:34
  • Hi @Leftium, thank you for your suggestion. I strangely thought of something similar to this from the previous suggestions. What I did was iterate through the list, and have switch the element with a random element in the list, which is basically what you just presented! It works and is O(n) as I wanted it to be. – Try Khov Feb 24 '19 at 06:54
  • @TryKhov: Cool! Take note that a naive version of this algorithm _overshuffles_ so some combinations are more common than others: not truly random. So that is why Fisher Yates is designed like it is. https://medium.com/@oldwestaction/randomness-is-hard-e085decbcbb2 – Leftium Feb 24 '19 at 06:58
0

Create two input arrays (or one array with duplicate elements). Randomly evict elements from the array and place them randomly in your 3 output arrays. You don’t need to shuffle them as you are picking elements randomly and placing randomly as well.

In your code you can check, if in output array, element is already present or not on a given index to avoid overriding.

Sagar Agrawal
  • 639
  • 1
  • 7
  • 17