Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного

def permutations[T](list:List[T]):List[List[T]] = list match {
  case List() => List()
  сase List(a) => List(List(a))
  case _ => list.flatMap(item => permutations(list.filter(_ != item)).map(permutation => item :: permutation))
}

println(permutations(List(1,2,3,4)).mkString("\n"))

Киньте ссылку, где почитать

На хаскеле

subs :: [a] -> [a]]
subs [] = []]
subs (x:xs) = yss ++ map (x yss
where yss = subs xs

interleave :: a -> [a] -> [a]]
interleave x [] = [x]]
interleave x (y:ys) = (x:y:ys) : map (y (interleave x ys)

perms :: [a] -> [a]]
perms [] = []]
perms (x:xs) = concat (map (interleave x) (perms xs))

На ерланге

perms([]) -> [ [] ];
perms(List) -> [ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ].

http://blogs.claritycon.com/blogs/peter_miller/archive/2007/10/10/3307.aspx

12-02-2009, avpavlov <12804@users.rsdn.ru> пишет:
>
> Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного
>
>

> def permutations[T](list:List[T]):List[List[T]] = list match {
>   case List() => List()
>   сase List(a) => List(List(a))
>   case _ => list.flatMap(item => permutations(list.filter(_ != item)).map(permutation => item :: permutation))
> }
>
> println(permutations(List(1,2,3,4)).mkString("\n"))
>

>
> Киньте ссылку, где почитать

A>Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного

Можно, в принципе. Только стек придётся эмулировать самостоятельно и таскать в качестве параметра.

Здравствуйте, avpavlov, Вы писали:

A>Киньте ссылку, где почитать
В стандартной библиотеке C++ есть функция next_permutation. Добрые люди говорят, что использует она некий algorithm L, придуманный Кнутом.

Здравствуйте, avpavlov, Вы писали:
A>Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного.

В принципе можно написать как угодно, а потом прогнать через CPS-трансформер.

SP>perms :: [a] -> [a]]
SP>perms [] = []]
SP>perms (x:xs) = concat (map (interleave x) (perms xs))

А где здесь хвостовая рекурсия?

SP>perms([]) -> [ [] ];
SP>perms(List) -> [ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ].

Синтаксис Эрланга мне не совсем понятен, но хвостовая рекурсия тут тоже не слишком очевидна. Или Эрланг всё таки достаточно умён, и преобразует в хвостовую рекурсию?

Здравствуйте, thesz, Вы писали:

A>>Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного

T>Можно, в принципе. Только стек придётся эмулировать самостоятельно и таскать в качестве параметра.

Да, я такой вариант рассматривал, только жертвовать читаемостью ради хвостовой рекурсии не хочется

Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, avpavlov, Вы писали:

A>>Киньте ссылку, где почитать
PM>В стандартной библиотеке C++ есть функция next_permutation. Добрые люди говорят, что использует она некий algorithm L, придуманный Кнутом.

В википедии есть алгоритм вообще без рекурсии, но выглядит он как чёрная магия. Я всё-таки голосую за легкочитаемость кода

http://en.wikipedia.org/wiki/Permutation

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, avpavlov, Вы писали:
A>>Не силён я в сферических алгоритмах, так что не знаю, существует ли такой? Своим умом допёр только до обычного рекурсивного.

MC>В принципе можно написать как угодно, а потом прогнать через CPS-трансформер.

Спасибо!

В действительности идея CPS довольно простая, будет время посижу подумаю как переписать в CPS стиле без трансформера (для самообразования )

13-02-2009, avpavlov <12804@users.rsdn.ru> пишет:
>
> SP>perms :: [a] -> [a]]
> SP>perms [] = []]
> SP>perms (x:xs) = concat (map (interleave x) (perms xs))
>
> А где здесь хвостовая рекурсия?
>
> SP>perms([]) -> [ [] ];
> SP>perms(List) -> [ [Head | Tail] || Head <- List, Tail <- perms(List--[Head]) ].
>
> Синтаксис Эрланга мне не совсем понятен, но хвостовая рекурсия тут тоже не слишком очевидна. Или Эрланг всё таки достаточно умён, и преобразует в хвостовую рекурсию?
>

Да эт я облажался