Need an algorithm for to shuffle elements of 5 arrays, each with the same 5 elements, such that no two arrays have the same element at the same index

Question

I've the following five arrays

var E1 = ["A", "B", "C", "D", "E"]
var E2 = ["A", "B", "C", "D", "E"]
var E3 = ["A", "B", "C", "D", "E"]
var E4 = ["A", "B", "C", "D", "E"]
var E5 = ["A", "B", "C", "D", "E"]

Each array have the same five elements namely "A", "B", "C", "D" and "E". I want to write an algorithm to sort the elements in all the arrays such that no two arrays have the same element (let's say "A") at the same index.

A sort of the sample output that will work for me will be like:

var E1 = ["A", "B", "C", "D", "E"]
var E2 = ["B", "C", "D", "E", "A"]
var E3 = ["C", "D", "E", "A", "B"]
var E4 = ["D", "E", "A", "B", "C"]
var E5 = ["E", "A", "B", "C", "D"]

I've tried to solve this but couldn't complete. I've just written a shuffling function for sorting the elements of two arrays(E1 and E2).

var E1 = ["A", "B", "C", "D", "E"]
var E2 = ["A", "B", "C", "D", "E"]
var E3 = ["A", "B", "C", "D", "E"]
var E4 = ["A", "B", "C", "D", "E"]
var E5 = ["A", "B", "C", "D", "E"]

func shuffledArrays(var array1: [String],var array2: [String]) {


if array1[0] == array2[0] || array1[1] == array2[1] || array1[2] == array2[2] || array1[3] == array2[3] || array1[4] == array2[4] {

    shuffled1 = GKRandomSource.sharedRandom().arrayByShufflingObjectsInArray(array1)
    shuffled2 = GKRandomSource.sharedRandom().arrayByShufflingObjectsInArray(array2)

    var array3 = shuffled1 as! [String]
    var array4 = shuffled2 as! [String]

} else {
    var array3 = array1
    var array4 = array2
}

array1 = array3
    array2 = array4
}

// Now calling the function on arrays E1 and E2
    shuffledArrays(E1, array2: E2)
    print(E1)
    print(E2)

With this code I'm getting the following error on Xcode Playground. While sometimes the error is removed and the output is correct at lines 102 and 103 but still I'm unable to extract that output out and save it permanently into E1 and E2 respectively. Please help me with the whole algorithm in arranging the five arrays' elements.

Thanks

Answer 1

Since you know arrays E1, ..., E5 to hold identical entries (in identical order), you needn't explicitly hold the arrays E2 through E5 (since you know these are value-equal to E1).

Hence, you could simply define a shift function and create E2 through E5 by repeated shifting of previous array.

import GameplayKit

func shiftByOne (arr: [String]) -> [String] {
    var shiftedArr = arr
    shiftedArr.insert(shiftedArr.popLast()!, atIndex: 0)
    return shiftedArr
}

var E1 = ["A", "B", "C", "D", "E"]
E1 = GKRandomSource.sharedRandom().arrayByShufflingObjectsInArray(E1) as! [String]
var E2 = shiftByOne(E1)
var E3 = shiftByOne(E2)
var E4 = shiftByOne(E3)
var E5 = shiftByOne(E4)

/** Result without initial shuffle:
E1 = ["A", "B", "C", "D", "E"]
E2 = ["B", "C", "D", "E", "A"]
E3 = ["C", "D", "E", "A", "B"]
E4 = ["D", "E", "A", "B", "C"]
E5 = ["E", "A", "B", "C", "D"] */

This method starts with E1 (possibly shuffling only this array), and guarantees that E2 through E5 are constructed to all differ, w.r.t. order, from each other.

As noted by R Menke below, if you shuffle array E1, the same behaviour will hold (however with shuffled initial array). Here I've used the same shuffler as in your example, but for a more Swifty approach, see e.g.:

• How do I shuffle an array in Swift?

Answer 2

As far as I can see you can make it this way:

1. Take a valid solution (just like the example you gave)
2. shuffle the columns (this can only lead to valid solutions)
3. shuffle the rows (this can only lead to valid solutions)

This way you can get all possible solutions.

For example, starting with a valid solution.

["A", "B", "C", "D", "E"]
["B", "C", "D", "E", "A"]
["C", "D", "E", "A", "B"]
["D", "E", "A", "B", "C"]
["E", "A", "B", "C", "D"]

Shuffle the rows.

["C", "D", "E", "A", "B"]
["B", "C", "D", "E", "A"]
["A", "B", "C", "D", "E"]
["D", "E", "A", "B", "C"]
["E", "A", "B", "C", "D"]

Then shuffle the columns.

["C", "E", "A", "D", "B"]
["B", "D", "E", "C", "A"]
["A", "C", "D", "B", "E"]
["D", "A", "B", "E", "C"]
["E", "B", "C", "A", "D"]

This guarantees no two arrays have the same element in the same index and they're randomized.

Here is an example in Ruby. The algorithm is applicable to any language.

# Initialize the first row of the matrix
matrix = []
matrix[0] = ('A'..'E').to_a

size = matrix[0].size

# Initialize the rotated array
for i in 1..size-1
  matrix[i] = matrix[i-1].rotate
end

puts "Original matrix"
for x in matrix
  puts x.inspect
end

# Shuffle the indexes of the rows and columns
rows = (0..size-1).to_a.shuffle
cols = (0..size-1).to_a.shuffle

# Shuffle the rows
for i in 0..size-1
  row1 = i
  row2 = rows[i]
  tmp = matrix[row1]
  matrix[row1] = matrix[row2]
  matrix[row2] = tmp
end

# Shuffle the columns.
for i in 0..size-1
  col1 = i
  col2 = cols[i]

  for j in 0..size-1
    tmp = matrix[j][col1]
    matrix[j][col1] = matrix[j][col2]
    matrix[j][col2] = tmp
  end
end

puts "Shuffled matrix"
for x in matrix
  puts x.inspect
end

@Schwern: Tanks for adding the example and the code.