Функция генератора перестановок F #

Question

Мне нужно создать список всех различных перестановок 1..n x 1..n, где первое значение не равно второму (т.е. генерировать 3 -> [(3,2) :: (3,1) :: (2,3): :( 2,1): :( 1,3): :( 1,2)]

Точный сценарий: у вас есть пул предметов (карт), и каждому игроку раздается по одному. Если игрок получает карту, ни один другой игрок не может получить эту карту (игнорируя масти на данный момент, если потребуется, я сделаю лут на 1-52 для сопоставления с реальными картами)

Я придумал следующее, которое в лучшем случае кажется грязным

 let  GenerateTuples (numcards: int) =
    let rec cellmaker (cardsleft: int) (cardval:int) = 
        if cardval = cardsleft  then (if cardval <= 0  then []  else cellmaker cardsleft (cardval-1) ) elif cardval <= 0  then [] else (cardsleft, cardval) :: cellmaker cardsleft (cardval-1)
    let rec generatelists (cardsleft:int) =
        cellmaker cardsleft numcards @ (if cardsleft > 1 then generatelists (cardsleft-1) else [])
    generatelists numcards

есть ли лучший способ сделать это?

Answer 1

Вы можете сделать это легко, используя списочные выражения:

let GenerateTuples (n:int) =
    [for i in 1..n do for j in 1..n do if i <> j then yield (i,j)]

Answer 2

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

let Permute n =
let rec Aux (x,y) =
    if (x,y) = (n,n) then
        []
    else
        let nextTuple = if y = n then ((x + 1),1) else (x,(y + 1))
        if x = y then
            Aux nextTuple
        else
            (x,y)::(Aux nextTuple)
Aux (1,1)

Это нерекурсивно, поэтому get переполняет стекпримерно на 500, на моей машине.Сделать эту функцию хвостовой рекурсивной почти тривиально.

Время для этого было очень интересным.Эта функция (хвостовая рекурсивная версия) заняла на 50% больше, чем оригинал, а императивное решение снова заняло примерно 3 раза!Да - оригинальное функциональное решение является самым быстрым, это следующее самое быстрое, и понимание императивного списка было самым медленным, приблизительно 1: 1,5 :: 4.Протестировано на самых разных наборах данных.