Перемешивание двух списков в другой список по определенным правилам

Я пытаюсь реализовать следующую программу в Ocaml: Напишите процедуру shuffle : α list → α list → α list, которая вернет список с элементами из 2 списков, перетасованных в соответствии со следующими правилами:

  • все списки из 2 входных списков находятся в выходных списках
  • элементы из обоих списков находятся в том же порядке, что и раньше
  • элементы хотя бы одного входного списка не находятся рядом друг с другом в выходном списке

Примеры результатов shuffle [5; 7; 0; 5] [3; 2; 8; 9; 3]:

  • [5; 3; 2; 7; 8; 9; 0; 3; 5]
  • [3; 5; 2; 7; 8; 0; 9; 5; 3]

Я знаю, как реализовать простую функцию перемешивания (взято из здесь):

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond

Не могли бы вы дать мне какие-либо советы о том, как мне уйти оттуда?


list shuffle ocaml
person syntagma    schedule 21.10.2014    source источник
comment
Я полагаю, длины двух входных списков должны быть одинаковыми?   -  person Jackson Tale    schedule 21.10.2014
comment
или вы имеете в виду, что в выходном списке, хотя бы для одного встроенного списка, элементы не стоят друг за другом? shuffle [1;2] [3;4;5;6] выведет [1;3;2;4;5;6], 5 и 6 являются соседями, но по крайней мере для [1;2] они не являются. ты имеешь в виду это?   -  person Jackson Tale    schedule 21.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вот простое случайное вкрапление, отвечающее первым двум требованиям:

let shuffle a b =
  let rec loop a b = match a, b with
     | [], r
     | r, [] -> r
     | x::xs, y::ys ->
        if Random.bool () then x::loop xs b
        else y::loop a ys in
  loop a b

Посмотрите, сможете ли вы адаптировать способ выбора списка, из которого нужно взять элемент, чтобы также выполнить третье требование. Возможно, вы захотите собрать некоторую информацию о списках перед началом, которую вы можете использовать при принятии решения.

person gsg    schedule 21.10.2014