Ruby Split число на единицу или половинки

Question

Мне нравится разделять счет на массив из n позиций.

Допустим, мой счет равен 11, а массив имеет размер 12. Тогда мне нравится иметь некоторый массив, который заполнен, например, 11 единицами или 10 единицами и 2 половинками (0.5). В итоге должно получиться 11.

Тогда возможные оценки:

size = 12
possible_scores = (0..size).step(0.5).to_a

Я могу создать массив из 12 позиций:

scores = Array.new(size) {0}

Я мог бы выбрать случайное значение из следующих возможных значений:

[0, 0.5, 1].sample

Я ищу эффективный способ получения случайного массива без большого количества переменных состояния, если это возможно. Я уже пытался сделать это в цикле while:

while score < 0

и уменьшите значение оценки со случайным значением и отследите установленные позиции массива. Но это стало довольно грязный кусок кода.

Есть идеи, как это решить? Спасибо!

Edit:

Для этого примера я хочу массив с суммой до 11. Так что любой из

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] 

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.5, 0.5] 

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1] 

Или любая комбинация, которая суммирует до 11.

Answer 1

Мне нравится ответ Кэри Свовеланд, но на самом деле это можно сделать, не генерируя множество решений.

Давайте рассмотрим несколько примеров.

Учитывая размер = 6 и счет = 3, без тасования, это возможные выходные данные (пронумерованы слева по причинам, которые станут очевидными):

i               ones halves zeroes
0│ 1 1 1 0 0 0    3     0      3
1│ 1 1 ½ ½ 0 0    2     2      2
2│ 1 ½ ½ ½ ½ 0    1     4      1
3│ ½ ½ ½ ½ ½ ½    0     6      0

Данный размер = 6 и оценка = 3,5:

i               ones halves zeroes
0│ 1 1 1 ½ 0 0    3     1      2
1│ 1 1 ½ ½ ½ 0    2     3      1
2│ 1 ½ ½ ½ ½ ½    1     5      0

Учитывая размер = 11 и оценка = 4,5:

i                         ones halves zeroes
0│ 1 1 1 1 ½ 0 0 0 0 0 0    4     1      6
1│ 1 1 1 ½ ½ ½ 0 0 0 0 0    3     3      5
2│ 1 1 ½ ½ ½ ½ ½ 0 0 0 0    2     5      4
3│ 1 ½ ½ ½ ½ ½ ½ ½ 0 0 0    1     7      3
4│ ½ ½ ½ ½ ½ ½ ½ ½ ½ 0 0    0     9      2

Данный размер = 12 и оценка = 11:

i                            ones halves zeroes
0│ 1 1 1 1 1 1 1 1 1 1 1 0    11     0      1
1│ 1 1 1 1 1 1 1 1 1 1 ½ ½    10     2      0

Вы видите узоры? После небольшого почесывания подбородка мы обнаруживаем следующие факты:

1. Количество возможных выходов ? для данного размера и балла определяется как:

   ? мин. (⌊ оценка ⌋, размер - ⌈ оценка ⌉) + 1

2. С увеличением ? количество единиц уменьшается. Количество единиц определяется как:

   Количество (1) ＝ ⌊ Оценка ⌋ - ?

3. С увеличением ? увеличивается число половинок (½). Количество половин определяется как:

   количество (½) ＝ 2 (? + мод ( оценка , 1))

   Другими словами, это 2? + 1, если оценка имеет дробную часть, или 2? в противном случае.

4. С увеличением ? уменьшается число нулей, определяемое как:

   количество (0) ＝ размер - ⌈ счет ⌉ - ?

Имея в виду эти четыре факта, мы можем сгенерировать любой из ? возможных выходных данных случайным образом, выбрав случайный ?, где 0 ≤ ? <?: </p>

? = случайный ([0..?))

Эти факты легко перевести на код Ruby:

n = [score.floor, size - score.ceil].min + 1
i = rand(n)
num_ones = score.floor - i
num_halves = 2 * (i + score % 1)
num_zeroes = (size - score.floor) - i

Теперь нам просто нужно немного его очистить и поместить в функцию, которая принимает size и score в качестве аргументов, превращает num_ones, num_halves и num_zeroes в массив 0 s, 0.5 s и 1 s, и перетасовывает результат:

def generate(size, score)
  init_ones = score.floor
  init_zeroes = size - score.ceil

  i = rand([init_ones, init_zeroes].min + 1)
  num_ones = init_ones - i
  num_halves = 2 * (i + score % 1)
  num_zeroes = init_zeroes - i

  [ *[1]*num_ones, *[0.5]*num_halves, *[0]*num_zeroes ].shuffle
end

generate(6, 3.5)
# => [0.5, 1, 0, 0.5, 0.5, 1]

Вы можете увидеть результат в действии на repl.it: https://repl.it/@jrunning/UnpleasantDimpledLegacysystem (Обратите внимание, что при запуске его на repl.it вывод отображается очень медленно. Это только потому, что repl.it выполняет код Ruby на сервер и передает результат обратно в браузер.)

Answer 2

Ruby предоставляет все, что вам нужно здесь, не нужно писать никакого алгоритмического кода. Array#repeated_combination ваш друг здесь:

[0, 0.5, 1].
  repeated_combination(12).    # 91 unique variant
  to_a.                        # unfortunately it cannot be lazy
  shuffle.                     # to randomize array outcome
  detect { |a| a.sum == 11 }.
  shuffle                      # to randomize numbers inside array
#⇒ [0.5, 0.5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

---

Sidenote: можно избежать необходимости перетасовать дважды (как массив сгенерированных массивов, так и полученный массив), используя Array#repeated_permutation, но это резко увеличит нагрузку на память и время исполнения.

Answer 3

Параметры и переменные

Дано:

• tot, желаемая сумма, целое или нечетное кратное 0.5;и
• size, общее количество 0, 0.5 и 1, что составляет tot, с требованием, что size >= tot.

мы определяем три переменные:

• n0 равно числу нулей;
• n0pt5_pairs равноколичество пар 0.5 х;и
• n1 равно числу единиц.

Случай 1: tot является целым числом

Нам требуется:

0 <= n0pt5_pairs <= [tot, size-tot].min

Обратите внимание, потому что n1 = tot - n0pt5_pairs, 2 * n0pt5_pairs + n1 = n0pt5_pairs + tot > size, если n0pt5_pairs > size-tot.Таким образом, общее число 0.5 и единиц превышает size, если число 0.5 пар превышает size-tot.

При заданном значении для n0pt5_pairs, которое удовлетворяет вышеуказанному требованию,n0 и n1 определены:

n1 = tot - n0pt5_pairs
n0 = size - 2*n0pt5_pairs - n1
   = size - tot - n0pt5_pairs

Поэтому мы можем случайным образом выбрать случайную тройку [n0, 2*n0pt5_pairs, n1] следующим образом:

def random_combo(size, tot)
  n0pt5_pairs = rand(1+[tot, size-tot].min)
  [size-tot-n0pt5_pairs, 2*n0pt5_pairs, tot-n0pt5_pairs]
end

Например:

arr = random_combo(17, 11)
  #=> [3, 6, 8]

Используется для генерации массива

arr1 = [*[0]*arr[0], *[0.5]*arr[1], *[1]*arr[2]]
  #=> [0, 0, 0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1, 1, 1, 1, 1, 1, 1, 1] 

, который мы перемешиваем:

arr1.shuffle
  #=> [1, 0, 0.5, 1, 0.5, 0, 1, 1, 0, 1, 1, 1, 0.5, 0.5, 1, 0.5, 0.5]

Примечание arr1.size #=> 17 и arr.sum #=> 11.

Случай 2: tot - кратное 0,5

Если

tot = n + 0.5

, где n - целое число, каждая комбинация 0, 0.5 и 1 будут иметь по крайней мере один 0.5.Поэтому мы можем вычислить число 0 и 1 вместе с числом 0.5 , превышающим единицу .Для этого мы просто уменьшаем tot на 0.5 (делая его равным целому числу) и size на единицу, используем generate_for_integer для решения этой проблемы, затем для каждого массива из трех элементов, возвращаемого этим методом, увеличиваемколичество 0.5 по одному.

def generate(size, tot)
  return nil if size.zero?
  is_int = (tot == tot.floor)
  tot = tot.floor
  size -= 1 unless is_int 
  n0pt5_pairs = rand(1+[tot, size-tot].min)
  [*[0]*(size-tot-n0pt5_pairs), *[0.5]*(2*n0pt5_pairs + (is_int ? 0 : 1)),
   *[1]*(tot-n0pt5_pairs)].
  shuffle
end

ge = generate(17, 10)
  #=> [0, 1, 0, 1, 0.5, 0.5, 0, 0.5, 0.5, 1, 1, 1, 1, 0.5, 0.5, 0.5, 0.5] 
ge.size #=> 17 
ge.sum  #=> 10.0 

go = generate(17, 10.5)
  #=> [0.5, 0.5, 0.5, 1, 0, 0.5, 0.5, 1, 1, 0.5, 1, 1, 0.5, 1, 0.5, 0.5, 0] 
go.size #=> 17 
go.sum  #=> 10.5  

Answer 4

Если я получу точку, один из возможных вариантов может быть (грубая сила)

size = 12
sum = 11
tmp = Array.new(12){1}

loop do
  raise 'not possible' if tmp.sum < sum
  tmp[tmp.index(1)] = 0.5 if tmp.index(1)
  unless tmp.index(1)
    tmp[tmp.index(0.5)] = 0
  end
  break if tmp.sum == sum
end

tmp #=> [0.5, 0.5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
tmp.sum #=> 11.0