用条件打乱数组
Shuffling an array with a condition
这是一个数组：
scramble = [
"R", "U", "R' ", "U' ", "L", "L' ", "L2", "B", "B' ",
"B2", "F", "F' ", "F2", "R2", "U2", "D", "D' ", "D2"
]
我想用 "R"、"R' " 和 "R2" 在洗牌时不在一起的条件进行洗牌，其他字母也类似。
scramble.shuffle 会随机播放，但我该如何设置这样的条件？
Juksefantomet 不和谐地向我发送了这个解决方案，因为由于帐户锁定他不能 post 这里。
下面的代码块包含解决手头问题的替代方法。这包含一个零散的解决方案，以了解您通常如何处理上述复杂问题的步骤。
通过各个步骤，您可以了解每个条件如何必须提前知道并指定到最终数组不是 "illegal".
的程度
@illegal_order = ['1','2','3','4','5','6','7','8','9']
puts @illegal_order.count
puts "#{@illegal_order}"
@foo = []
# traverse the original array and append a random value from that into foo array
# this can of course and should be done in a loop where you check for duplicates
# this is done below in this example, fragmented to see the individual action
(0..@illegal_order.count).each do |add_value|
@temp = @illegal_order[rand(@illegal_order.count)]
unless @foo.count == @illegal_order.count
@foo.push(@temp)
end
end
# making sure it contains everything in the original array
@foo.each do |bar|
unless @illegal_order.include?(bar)
@approve = false
puts "Errored generation!"
end
end
# defining patterns, this can of course be extracted by the original array and be done alot cleaner
# but printing it out to better break it down
@pattern1 = [@illegal_order[0],@illegal_order[1],@illegal_order[2]]
@pattern2 = [@illegal_order[3],@illegal_order[4],@illegal_order[5]]
@pattern3 = [@illegal_order[6],@illegal_order[7],@illegal_order[8]]
# Let us step through the new array and use case to check for various conditions that would flag the new array as invalid
@foo.each do |step|
# setting a temp pattern based on current state
@temp_pattern = [@foo[step.to_i-1],@illegal_order[step.to_i],@illegal_order[step.to_i+1]]
case step
when @temp_pattern == @pattern1
@illegalpatterns = true
when @temp_pattern == @pattern2
@illegalpatterns = true
when @temp_pattern == @pattern3
@illegalpatterns = true
end
# checking the foo array if it contains duplicates, if yes, set conditional to true
@illegal_order.each do |count|
if @foo.count(count) > 1
@duplicates = true
end
end
end
# printing out feedback based on duplicates or not, this is where you rescramble the array if duplicate found
(@duplicates == true) ? (puts "dupes found") : (puts "looks clear. no duplicates")
# printing out feedback based on illegal patterns or not, this is where you rescramble the array if duplicate found
(@illegalpatterns == true) ? (puts "illegal patterns found") : (puts "looks clear, no illegal patterns")
puts "#{@foo}"
让我们推导出一个通用的解决方案。
给定一个由元素组组成的二维数组，return 一个随机元素数组，使得没有两个连续元素属于同一组。
例如：
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
预期输出：
["F'", "U'", "R'", "L2", "R2", "D2", "F2", "R", "L", "B", "F", "L'", "D'", "B'", "U2", "B2", "U", "D"]
TL;DR代码:
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
ans = []
total = all_groups.map(&:length).reduce(:+)
# Initial shuffling
all_groups = all_groups.each { |i| i.shuffle! }.shuffle
until all_groups.empty?
# Select and pop last group
last_group = all_groups.pop
# Insert last element to our ans, and remove from group
ans.push(last_group.pop)
total -= 1
# Shuffle remaining groups
all_groups.shuffle!
# Check if any group has reached critical state
length_of_longest_group = all_groups.reduce(0) { |len, i| [len, i.length].max }
if length_of_longest_group * 2 == total + 1
# Move that group to last
# This ensures that next element picked is from this group
longest_group = all_groups.detect { |i| i.length == length_of_longest_group }
all_groups.delete(longest_group)
all_groups.push(longest_group)
end
# Insert the last group at first place. This ensures that next element
# is not from this group.
all_groups.unshift(last_group) unless last_group.empty?
end
puts ans.inspect
示例：
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
# Output 1:
ans = ["B'", "U'", "L'", "U2", "R", "B2", "F2", "R2", "D2", "L2", "D", "R'", "U", "F'", "D'", "L", "F", "B"]
# Output 2:
ans = ["U'", "R", "D", "R'", "U", "D2", "B2", "D'", "L", "B", "L2", "B'", "U2", "F'", "L'", "F", "R2", "F2"]
# Output 3:
ans = ["B", "D", "R'", "D'", "B'", "R", "F2", "L", "D2", "B2", "F'", "R2", "U'", "F", "L'", "U2", "L2", "U"]
# Output 4:
ans = ["U'", "F'", "R2", "B2", "D", "L2", "B'", "U", "R", "B", "R'", "L'", "D'", "U2", "F", "D2", "F2", "L"]
# Output 5:
ans = ["U2", "F2", "L'", "F'", "R'", "F", "D'", "B2", "D2", "L", "B", "D", "L2", "B'", "R", "U", "R2", "U'"]
all_groups = [
['a', 'aa', 'aaa', 'A', 'AA', 'AAA'],
['b', 'bb', 'bbb', 'B', 'BB', 'BBB'],
['c', 'cc', 'ccc', 'C', 'CC', 'CCC']
]
ans = ["c", "AAA", "B", "ccc", "bbb", "C", "AA", "CC", "aa", "BB", "CCC", "bb", "cc", "A", "BBB", "a", "b", "aaa"]
all_groups = [
['r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7', 'r8'],
['b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8']
]
# Output1:
ans = ["r2", "b7", "r1", "b5", "r7", "b6", "r3", "b8", "r4", "b3", "r5", "b1", "r6", "b4", "r8", "b2"]
# Output2:
ans = ["b6", "r8", "b2", "r1", "b4", "r2", "b8", "r7", "b3", "r4", "b5", "r5", "b7", "r3", "b1", "r6"]
解释：
首先，让我们打乱输入数据。首先我们打乱每个组，然后我们打乱外部数组。
all_groups = all_groups.each { |i| i.shuffle! }.shuffle
现在我们的数组如下所示：
[["B", "B2", "B'"],
["F'", "F", "F2"],
["L", "L2", "L'"],
["R2", "R'", "R"],
["D", "D'", "D2"],
["U'", "U", "U2"]]
现在，如果我们按列优先顺序遍历这个数组，我们会得到相当不错的元素混洗，其中没有两个连续的元素属于同一组。
["B", "F'", "L", "R2", "D", "U'", "B2", "F", "L2", "R'", "D'", "U", "B'", "F2", "L'", "R", "D2", "U2"]
但这唯一的缺陷是特定组的所有元素都是等距的。让我们改进一下。
所以我们有一组组。让 select 组中的任何一个，然后 select 该组中的最后一个元素，并将此元素添加到我们的答案数组中。现在打乱二维数组并重复，直到所有元素都 selected.
此外，我们不希望任何两个连续的元素属于同一组，因此我们需要确保元素的下一个 selection 来自其他组。那么这个策略怎么样：
始终从我们的二维数组中选择最后一组，然后一旦我们洗牌，我们将确保这组不是二维数组中的最后一组。
伪代码方面：
1. Select last group from 2d array.
2. Remove an element from this group.
3. Shuffle the order of other groups in 2d array
4. Insert the selected group at begining.
例如，让我们从这个二维数组开始：
[["D", "D'", "D2"],
["U", "U'", "U2"],
["B2", "B", "B'"],
["F2", "F", "F'"],
["L'", "L", "L2"],
["R'", "R2", "R"]]
最后一组：["R'", "R2", "R"]
删除的元素：("R")
打乱二维数组剩余组的顺序：
[["L'", "L", "L2"],
["B2", "B", "B'"],
["D", "D'", "D2"],
["U", "U'", "U2"],
["F2", "F", "F'"]]
插入弹出组（我们从中提取元素的组）后的二维数组
[["R'", "R2"],
["L'", "L", "L2"],
["B2", "B", "B'"],
["D", "D'", "D2"],
["U", "U'", "U2"],
["F2", "F", "F'"]]
现在，由于我们的逻辑 select 是最后一组，然后将其插入开头，我们可以确保同一组的两个元素永远不会在连续两个回合中被选取。
一个catch：可能有一个组永远到不到最后一个位置，所以这个组永远不会收缩，一旦元素个数太少就会强制连续拾取它的元素.
例如，在以下输入上观察上述算法的 4 次迭代的输出：
[['a', 'aa', 'aaa', 'A', 'AA', 'AAA'],
['b', 'bb', 'bbb', 'B', 'BB', 'BBB'],
['c', 'cc', 'ccc', 'C', 'CC', 'CCC']]
# Output 1: in this 'a' & 'aaa' are together
["CC", "bb", "C", "BB", "aa", "bbb", "AA", "CCC", "b", "c", "B", "cc", "A", "BBB", "AAA", "ccc", "a", "aaa"]
# Output 2: in this 'b' & 'BB' are together
["cc", "A", "B", "c", "AAA", "C", "a", "ccc", "bbb", "CCC", "aaa", "bb", "CC", "aa", "BBB", "AA", "b", "BB"]
# Output 3: this is perfect
["CCC", "BB", "a", "c", "BBB", "aa", "bbb", "A", "bb", "ccc", "B", "CC", "AAA", "b", "AA", "cc", "aaa", "C"]
# Output 4: in this 'c' & 'cc' are together
["CC", "bb", "AA", "b", "aa", "BBB", "aaa", "bbb", "CCC", "B", "A", "BB", "C", "a", "ccc", "AAA", "c", "cc"]
因此，当 number of elements in a group 与 total no of elements 的比率增加时，同一组的两个元素有可能组合在一起。嗯，让我们进一步改进：
由于元素数量最多的组最有可能将两个元素连续组合，让我们研究一下这样的组。即具有最大元素数的组。
比方说，有一个包含 X 个元素的组。那么要求none个X元素连续的其他类型元素的最小个数是多少？简单右：在该组的每对元素之间插入一个不同的元素。
x * x * x * x * x * x
所以我们意识到，如果组有 X 个元素，它至少需要 (X-1) 个其他类型的元素，这样这个组中没有两个元素是连续的。
在数学上，条件可以表示为：
number_of_elements_in_longest_group == number_of_other_type_of_elements + 1
=> number_of_elements_in_longest_group == (total_number_of_elements - number_of_elements_in_longest_group) + 1
=> number_of_elements_in_longest_group * 2 == total_number_of_elements + 1
回到我们的算法，让我们添加一个条件，即在任何时间点，如果剩余项目的数量比最大组中的元素数量少 1，那么我们必须确保选择的下一个元素来自这个最大的群体
这是一个数组：
scramble = [
"R", "U", "R' ", "U' ", "L", "L' ", "L2", "B", "B' ",
"B2", "F", "F' ", "F2", "R2", "U2", "D", "D' ", "D2"
]
我想用 "R"、"R' " 和 "R2" 在洗牌时不在一起的条件进行洗牌，其他字母也类似。
scramble.shuffle 会随机播放，但我该如何设置这样的条件？
Juksefantomet 不和谐地向我发送了这个解决方案，因为由于帐户锁定他不能 post 这里。
下面的代码块包含解决手头问题的替代方法。这包含一个零散的解决方案，以了解您通常如何处理上述复杂问题的步骤。
通过各个步骤，您可以了解每个条件如何必须提前知道并指定到最终数组不是 "illegal".
的程度 @illegal_order = ['1','2','3','4','5','6','7','8','9']
puts @illegal_order.count
puts "#{@illegal_order}"
@foo = []
# traverse the original array and append a random value from that into foo array
# this can of course and should be done in a loop where you check for duplicates
# this is done below in this example, fragmented to see the individual action
(0..@illegal_order.count).each do |add_value|
@temp = @illegal_order[rand(@illegal_order.count)]
unless @foo.count == @illegal_order.count
@foo.push(@temp)
end
end
# making sure it contains everything in the original array
@foo.each do |bar|
unless @illegal_order.include?(bar)
@approve = false
puts "Errored generation!"
end
end
# defining patterns, this can of course be extracted by the original array and be done alot cleaner
# but printing it out to better break it down
@pattern1 = [@illegal_order[0],@illegal_order[1],@illegal_order[2]]
@pattern2 = [@illegal_order[3],@illegal_order[4],@illegal_order[5]]
@pattern3 = [@illegal_order[6],@illegal_order[7],@illegal_order[8]]
# Let us step through the new array and use case to check for various conditions that would flag the new array as invalid
@foo.each do |step|
# setting a temp pattern based on current state
@temp_pattern = [@foo[step.to_i-1],@illegal_order[step.to_i],@illegal_order[step.to_i+1]]
case step
when @temp_pattern == @pattern1
@illegalpatterns = true
when @temp_pattern == @pattern2
@illegalpatterns = true
when @temp_pattern == @pattern3
@illegalpatterns = true
end
# checking the foo array if it contains duplicates, if yes, set conditional to true
@illegal_order.each do |count|
if @foo.count(count) > 1
@duplicates = true
end
end
end
# printing out feedback based on duplicates or not, this is where you rescramble the array if duplicate found
(@duplicates == true) ? (puts "dupes found") : (puts "looks clear. no duplicates")
# printing out feedback based on illegal patterns or not, this is where you rescramble the array if duplicate found
(@illegalpatterns == true) ? (puts "illegal patterns found") : (puts "looks clear, no illegal patterns")
puts "#{@foo}"
让我们推导出一个通用的解决方案。
给定一个由元素组组成的二维数组，return 一个随机元素数组，使得没有两个连续元素属于同一组。
例如：
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
预期输出：
["F'", "U'", "R'", "L2", "R2", "D2", "F2", "R", "L", "B", "F", "L'", "D'", "B'", "U2", "B2", "U", "D"]
TL;DR代码:
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
ans = []
total = all_groups.map(&:length).reduce(:+)
# Initial shuffling
all_groups = all_groups.each { |i| i.shuffle! }.shuffle
until all_groups.empty?
# Select and pop last group
last_group = all_groups.pop
# Insert last element to our ans, and remove from group
ans.push(last_group.pop)
total -= 1
# Shuffle remaining groups
all_groups.shuffle!
# Check if any group has reached critical state
length_of_longest_group = all_groups.reduce(0) { |len, i| [len, i.length].max }
if length_of_longest_group * 2 == total + 1
# Move that group to last
# This ensures that next element picked is from this group
longest_group = all_groups.detect { |i| i.length == length_of_longest_group }
all_groups.delete(longest_group)
all_groups.push(longest_group)
end
# Insert the last group at first place. This ensures that next element
# is not from this group.
all_groups.unshift(last_group) unless last_group.empty?
end
puts ans.inspect
示例：
all_groups = [
["R", "R'", "R2" ],
["L", "L'", "L2" ],
["U", "U'", "U2" ],
["D", "D'", "D2" ],
["F", "F'", "F2" ],
["B", "B'", "B2" ]
]
# Output 1:
ans = ["B'", "U'", "L'", "U2", "R", "B2", "F2", "R2", "D2", "L2", "D", "R'", "U", "F'", "D'", "L", "F", "B"]
# Output 2:
ans = ["U'", "R", "D", "R'", "U", "D2", "B2", "D'", "L", "B", "L2", "B'", "U2", "F'", "L'", "F", "R2", "F2"]
# Output 3:
ans = ["B", "D", "R'", "D'", "B'", "R", "F2", "L", "D2", "B2", "F'", "R2", "U'", "F", "L'", "U2", "L2", "U"]
# Output 4:
ans = ["U'", "F'", "R2", "B2", "D", "L2", "B'", "U", "R", "B", "R'", "L'", "D'", "U2", "F", "D2", "F2", "L"]
# Output 5:
ans = ["U2", "F2", "L'", "F'", "R'", "F", "D'", "B2", "D2", "L", "B", "D", "L2", "B'", "R", "U", "R2", "U'"]
all_groups = [
['a', 'aa', 'aaa', 'A', 'AA', 'AAA'],
['b', 'bb', 'bbb', 'B', 'BB', 'BBB'],
['c', 'cc', 'ccc', 'C', 'CC', 'CCC']
]
ans = ["c", "AAA", "B", "ccc", "bbb", "C", "AA", "CC", "aa", "BB", "CCC", "bb", "cc", "A", "BBB", "a", "b", "aaa"]
all_groups = [
['r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7', 'r8'],
['b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8']
]
# Output1:
ans = ["r2", "b7", "r1", "b5", "r7", "b6", "r3", "b8", "r4", "b3", "r5", "b1", "r6", "b4", "r8", "b2"]
# Output2:
ans = ["b6", "r8", "b2", "r1", "b4", "r2", "b8", "r7", "b3", "r4", "b5", "r5", "b7", "r3", "b1", "r6"]
解释：
首先，让我们打乱输入数据。首先我们打乱每个组，然后我们打乱外部数组。
all_groups = all_groups.each { |i| i.shuffle! }.shuffle
现在我们的数组如下所示：
[["B", "B2", "B'"],
["F'", "F", "F2"],
["L", "L2", "L'"],
["R2", "R'", "R"],
["D", "D'", "D2"],
["U'", "U", "U2"]]
现在，如果我们按列优先顺序遍历这个数组，我们会得到相当不错的元素混洗，其中没有两个连续的元素属于同一组。
["B", "F'", "L", "R2", "D", "U'", "B2", "F", "L2", "R'", "D'", "U", "B'", "F2", "L'", "R", "D2", "U2"]
但这唯一的缺陷是特定组的所有元素都是等距的。让我们改进一下。
所以我们有一组组。让 select 组中的任何一个，然后 select 该组中的最后一个元素，并将此元素添加到我们的答案数组中。现在打乱二维数组并重复，直到所有元素都 selected.
此外，我们不希望任何两个连续的元素属于同一组，因此我们需要确保元素的下一个 selection 来自其他组。那么这个策略怎么样：
始终从我们的二维数组中选择最后一组，然后一旦我们洗牌，我们将确保这组不是二维数组中的最后一组。
伪代码方面：
1. Select last group from 2d array.
2. Remove an element from this group.
3. Shuffle the order of other groups in 2d array
4. Insert the selected group at begining.
例如，让我们从这个二维数组开始：
[["D", "D'", "D2"],
["U", "U'", "U2"],
["B2", "B", "B'"],
["F2", "F", "F'"],
["L'", "L", "L2"],
["R'", "R2", "R"]]
最后一组：["R'", "R2", "R"]
删除的元素：("R")
打乱二维数组剩余组的顺序：
[["L'", "L", "L2"],
["B2", "B", "B'"],
["D", "D'", "D2"],
["U", "U'", "U2"],
["F2", "F", "F'"]]
插入弹出组（我们从中提取元素的组）后的二维数组
[["R'", "R2"],
["L'", "L", "L2"],
["B2", "B", "B'"],
["D", "D'", "D2"],
["U", "U'", "U2"],
["F2", "F", "F'"]]
现在，由于我们的逻辑 select 是最后一组，然后将其插入开头，我们可以确保同一组的两个元素永远不会在连续两个回合中被选取。
一个catch：可能有一个组永远到不到最后一个位置，所以这个组永远不会收缩，一旦元素个数太少就会强制连续拾取它的元素. 例如，在以下输入上观察上述算法的 4 次迭代的输出：
[['a', 'aa', 'aaa', 'A', 'AA', 'AAA'],
['b', 'bb', 'bbb', 'B', 'BB', 'BBB'],
['c', 'cc', 'ccc', 'C', 'CC', 'CCC']]
# Output 1: in this 'a' & 'aaa' are together
["CC", "bb", "C", "BB", "aa", "bbb", "AA", "CCC", "b", "c", "B", "cc", "A", "BBB", "AAA", "ccc", "a", "aaa"]
# Output 2: in this 'b' & 'BB' are together
["cc", "A", "B", "c", "AAA", "C", "a", "ccc", "bbb", "CCC", "aaa", "bb", "CC", "aa", "BBB", "AA", "b", "BB"]
# Output 3: this is perfect
["CCC", "BB", "a", "c", "BBB", "aa", "bbb", "A", "bb", "ccc", "B", "CC", "AAA", "b", "AA", "cc", "aaa", "C"]
# Output 4: in this 'c' & 'cc' are together
["CC", "bb", "AA", "b", "aa", "BBB", "aaa", "bbb", "CCC", "B", "A", "BB", "C", "a", "ccc", "AAA", "c", "cc"]
因此，当 number of elements in a group 与 total no of elements 的比率增加时，同一组的两个元素有可能组合在一起。嗯，让我们进一步改进：
由于元素数量最多的组最有可能将两个元素连续组合，让我们研究一下这样的组。即具有最大元素数的组。
比方说，有一个包含 X 个元素的组。那么要求none个X元素连续的其他类型元素的最小个数是多少？简单右：在该组的每对元素之间插入一个不同的元素。
x * x * x * x * x * x
所以我们意识到，如果组有 X 个元素，它至少需要 (X-1) 个其他类型的元素，这样这个组中没有两个元素是连续的。
在数学上，条件可以表示为：
number_of_elements_in_longest_group == number_of_other_type_of_elements + 1
=> number_of_elements_in_longest_group == (total_number_of_elements - number_of_elements_in_longest_group) + 1
=> number_of_elements_in_longest_group * 2 == total_number_of_elements + 1
回到我们的算法，让我们添加一个条件，即在任何时间点，如果剩余项目的数量比最大组中的元素数量少 1，那么我们必须确保选择的下一个元素来自这个最大的群体