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.

Answer 3

i like Leo's answer. My answer is almost 'pure' swift (import Foundation is there due to arc4random_uniform function)

import Foundation // arc4random_uniform

let arr = Array(1...5)
var result: [[Int]] = []
repeat {
    let r = arr.sort { (a, b) -> Bool in
        arc4random_uniform(2) == 0
    }
    if !result.contains({ (s) -> Bool in
        s == r
    }) {
        result.append(r)
    }
} while result.count < 6

print(result)
// [[2, 3, 1, 4, 5], [4, 2, 1, 3, 5], [2, 1, 3, 4, 5], [2, 3, 1, 5, 4], [2, 4, 5, 1, 3], [2, 1, 4, 3, 5]]

Answer 4

I am answering from an iPhone, so I have no compiler to test some code. I can just give you a basic idea how to solve this.

Create a dictionary where the key is one element (like "A") and the value is an array of already added indices.

var dict = [String : [Int]]()

Then iterate thru all 5 arrays and append each element. Before appending it check in the dictionary if this element is already added somewhere else at the same index. If not you can add it, if yes, append another element and add the added index to the dict.

I hope you get the idea.

Answer 5

First some shortcuts :

• Construct a type that easily displays a nested array in rows / columns.
• Have a way to detect duplicate elements in columns (same element with same index in different row)

This can be found here

I did not include it in the answer because it is not part of the algorithm.

---

Extend Array to implement a function only when the Array is multidimensional and it's nested Element is Equatable.

extension Array where Element : _ArrayType, Element.Element : Equatable {

Self will be of type Array<Element> and will not recognise that it is cast-able to Array<Array<Element.Element>>. See the gist for the conversion.

    func entropy() -> [[Element.Element]]? { // returns nil when it is impossible

Create a matrix from the array.

        var matrix = self.matrix() // see gist for Matrix type

This nested function does the actual Array mutations. It swaps two elements in a row.

        func swap(row r:Int,column c:Int) {

            let nextColumn : Int = {
                if (c + 1) < matrix[r].count {
                    return c + 1
                } else {
                    return 0
                }
            }()

            let element = matrix[r][c]
            let neighbour = matrix[r][nextColumn]
            matrix[r][c] = neighbour
            matrix[r][nextColumn] = element

        }

This is the looping logic:

As long as the columns of the matrix contain duplicates -> go over each column -> find a duplicate -> swap it with a neighbour.

It is not very efficient. But you can try different functions to mutate the rows and see what works best.

        while matrix.columnsContainDuplicates() {
            for c in 0..<matrix.columns.count {
                let column = matrix.columns[c]
                if let dupeIndex = column.indexOfDuplicate() {
                    swap(row: dupeIndex, column: c)
                }
            }
        }

        return matrix.rows
    }
}

---

Complete code with and extra nested function to check if it is solvable. There might be other reasons why it might not be solvable.

extension Array where Element : _ArrayType, Element.Element : Equatable {

    func entropy() -> [[Element.Element]]? {

        var matrix = self.matrix() // this comes from an extension to Array: if nested, can be converted to a matrix

        // is there a possible configuration where no column has duplicates?
        func solvable() -> Bool {
            // this just checks if element x does not appear more than there are possible indexes.
            var uniqueElements : [Element.Element] = []
            var occurences : [Int] = []

            for row in matrix.rows {
                var rowCopy = row
                while let pop = rowCopy.popLast() {
                    if let index = uniqueElements.indexOf(pop) {
                        occurences[index] += 1
                        occurences[index]
                    } else {
                        uniqueElements.append(pop)
                        occurences.append(1)
                    }
                }
            }

            var highest = 0
            for times in occurences {
                if highest < times { highest = times }
            }

            if highest > matrix.columns.count {
                highest
                return false
            }

            return true
        }

        func swap(row r:Int,column c:Int) {

            let nextColumn : Int = {
                if (c + 1) < matrix[r].count {
                    return c + 1
                } else {
                    return 0
                }
            }()

            let element = matrix[r][c]
            let neighbour = matrix[r][nextColumn]
            matrix[r][c] = neighbour
            matrix[r][nextColumn] = element

        }

        guard solvable() else {
            return nil
        }

        while matrix.columnsContainDuplicates() {
            for c in 0..<matrix.columns.count {
                let column = matrix.columns[c]
                if let dupeIndex = column.indexOfDuplicate() {
                    swap(row: dupeIndex, column: c)
                }
            }
        }

        return matrix.rows
    }
}

Tests :

let test = [[4,3,2,1],[5,2,3,4],[1,6,3,4],[1,2,3,4]] // 8 loops
test.entropy() // [[3, 4, 1, 2], [4, 3, 2, 5], [6, 1, 4, 3], [1, 2, 3, 4]]

let test2 = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] // 8 loops
test2.entropy() // [[3, 4, 1, 2], [4, 3, 2, 1], [2, 1, 4, 3], [1, 2, 3, 4]]