Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
3.8k views
in Technique[技术] by (71.8m points)

algorithm - Ruby. Shuffle the array so that there are no adjacent elements with the same value

An array of hashes is given (10 elements at least):

arr = [{letter: "a", number: "1"}, {letter: "a", number: "3"}, {letter: "b", number: "4"}, {letter: "b", number: "1"}, ..., {letter: "e", number: "2"} ]

The task is to shuffle the array so that there are no adjacent elements with the same 'letter' value.

So, the result should be like the following:

[{letter: "c", number: "4"}, {letter: "a", number: "1"}, {letter: "e", number: "2"}, {letter: "b", number: "1"}, ..., {letter: "a", number: "3"} ]

What is the simplest way to do that?

=== UPDATE ===

The number of repeated letters in the array is precisely known - it's 20% of the array length. So, the array looks like the following:

[
{letter: "a", number: "1"}, {letter: "a", number: "3"}, 
{letter: "b", number: "4"}, {letter: "b", number: "1"},
{letter: "c", number: "7"}, {letter: "c", number: "3"},
{letter: "d", number: "6"}, {letter: "d", number: "4"},
{letter: "e", number: "5"}, {letter: "e", number: "2"}
]

Or, its simplified version:

["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]

Or, for example, there is a simplified array containing 15 elements:

["a", "a", "a", "b", "b", "b", "c", "c", "c", "d", "d", "d", "e", "e", "e"]

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

The simple and maybe the less effective way could be the brute force.

So on a simplified version of the array, one can do:

ary = %w(a a c c b a s)

loop do
  break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
end

Some check should be added to assure that a solution exists, to avoid infinite loop.


Other (better?) way is to shuffle then find the permutation (no infinite loop) which satisfy the condition:
ary.shuffle!    
ary.permutation.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }

If a solution does not exist, it returns nil.


Run the the benchmark:
def looping
  ary = %w(a a c c b a s)
  loop do
    break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
  end
  ary
end

def shuffle_permute
  ary = %w(a a c c b a s)
  ary.shuffle!
  ary.permutation.lazy.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }
end

require 'benchmark'

n = 500
Benchmark.bm do |x|
  x.report { looping }
  x.report { shuffle_permute }
end

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

60 comments

57.0k users

...