а что непонятно? Итерация по первому элементу и рекурсивно всевозможные перестановки остальных элементов

Erlang'a не знаю, но судя по всему на Haskell это будет выглядеть так:

import Data.List

perms [] = [[]]
perms l = [h : t | h <- l, t <- perms (l \\ [h])]

Да, спасибо, это понятно.

Не понятна последовательность подстановки.

ghci> [[x,y] | x <- [1,2], y <- [1,2,3]]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]]
ghci> [[x,y,z] | x <- [1,2], y <- [3,4], z <- [5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
ghci> 

Так понятнее?

Вот как это будет выглядеть императивно на C#:

using System;
using System.Collections.Generic;
using System.Linq;

namespace test
{
	class Perms
	{
		public static IEnumerable<T> constructor<T> (T head, IEnumerable<T> tail)
		{
			var res = new List<T> ();
			res.Add (head);
			res.AddRange (tail);
			return res;
		}

		public static IEnumerable<IEnumerable<T>> GetPerms<T> (IEnumerable<T> l)
		{
			if (l.Count () == 0)
				return Enumerable.Empty<IEnumerable<T>> ();

			var result = new List<IEnumerable<T>> ();

			foreach (var h in l) {
				var c = GetPerms (l.Except (new []{h}));
				if (c.Count () == 0) {
					result.Add (constructor (h, Enumerable.Empty<T> ()));
				} else {
					foreach (var t in c) {
						result.Add (constructor (h, t));
					}
				}
			}
			return result;
		}
	}

	class Program
	{
		static void Main (string[] args)
		{
			var list = Perms.GetPerms ("123");
			foreach (var i in list) {
				var ii = i.ToArray ();
				for (var j = 0; j < ii.Length; ++j) {
					Console.Write (ii[j]);
					if (j < ii.Length - 1)
						Console.Write (",");
				}
				Console.WriteLine ();
			}
		}
	}
}

С вашим примером разобрался, а вот со своим ни как.

не так же будет?

import Data.List

perms [] = [[]]
perms l = [h : t | h <- l, t <- perms (l \\ [h])]


perms 123 = [1 : 23 | 1 <- 123, 23 <- perms (123 \\ [1])]

Помогите разобраться с кодом на эрланг!
Ну смотри, на хацкеле так, а на сишарпе так.

я один думаю, что это непедагогично?

Когда вызывается perms с аргументом "123":

на 1-м шаге h = 1, t = ["23", "32"], h комбинируется со всеми элементами списка t, получается список ["123", "132"];

на 2-м шаге h = 2, t = ["13", "31"], получается список ["213", "231"];

на 3-м шаге h = 3, t = ["12", "21"], получается список ["312", "321"];

В конце полученные списки склеиваются.

я один думаю, что это непедагогично?

List comprehension везде одинаковый, а с синтаксисом эрланга разбираться лень.

Не, ну я тупой.

как на первом вхождении получилось 23 и 32?

Когда вызывается perms с аргументом "123":

на 1-м шаге h = 1, t = ["23", "32"], h комбинируется со всеми элементами списка t, получается список ["123", "132"];

на 2-м шаге h = 2, t = ["13", "31"], получается список ["213", "231"];

на 3-м шаге h = 3, t = ["12", "21"], получается список ["312", "321"];

я один думаю, что это непедагогично?

Но зато интересно! Вот где питон слил:

>>> perms = lambda L : sum([ [ L[i]+l for l in perms(L[:i]+L[i+1:]) ] for i in range(len(L)) ], []) if L else ['']
>>> perms('123')
['123', '132', '213', '231', '312', '321']

как на первом вхождении получилось 23 и 32?

t <- perms (l \\ [h])
t присваивается результат рекурсивного вызова perms со списком "23" ("123" минус текущее значение h), т.е все перестановки списка "23" => ["23", "32"]

Вот где питон слил

ты это расскажи вот этому чуду. Чего-то меня все больше тянет в сторону F# какого-нибудь.

  def perms1[A](in:List[A]):List[List[A]]=
    in match{
      case a if a.isEmpty => List(List.empty[A])
      case _  => (for(x<-in) yield for(y<-perms1(in.diff(List(x)))) yield x::y).flatten.toList
    }

или так приятнее?

  def perms[A](in:List[A]):List[List[A]]=
    in match{
      case a if a.isEmpty => List(List.empty[A])
      case _  => in.flatMap(x=>perms(in.diff(List(x))).map(xs=>x::xs)).toList
    }

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

>>> from itertools import permutations
>>> ["".join(x) for x in permutations("123")]
['123', '132', '213', '231', '312', '321']

Все-таки сила питона — в библиотеке.

мда

"123".toList.permutations.toList

вот и все дела.

вот и все дела.

Это не равноценно, ведь ни пример на эрланге, ни пример на хаскелле не используют библиотечную функцию, иначе бы было просто

permutations "123"

В Эхо намылился?

Это Scala?

да, это она.

А я думаю, что си-шарп это пипец :/

perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

Гм. Странно, почему в нашем 21ом веке до сих пор живы языки программирования, позволящие написать код так, чтобы сразу небыло понятно, что вообще этот код делает?

А я думаю, что си-шарп это пипец :/

Здесь пример немного раздут, чтобы было понятнее. Но в любом случае, без pattern matching'a кода больше.

ты так говоришь, потому что в руби нет list comprehensions, и сам ты с хачкелем не знаком. а если есть понятие, что это, то даже я допетрил, что perms - это permutations, а синтаксис примерно одинаковый у всех спископостроителей.

Мне честно говоря такие вещи проще сделать руками, чем по библиотекам шарится;-)

Страсть хосподня... это какие то неправильные ЯП, и они делают неправильный код;-)

Вот, господа функционанисты и педонисты, наглядная вам демонстрация и без того очевидного (но не для вас) факта, что list comprehensions не являются интуитивно понятными, и что единственная их функция - запутывание кода до полной лапшеподобной нечитабельности.

Увы, какашкели с лишпиками и еблангами - далеко не единственные паталогически нечитабельные языки. Начинать чистку надо было бы с Си (и многих его производных) и Перла.

Если я не ошибаюсь, то даже тут как минимум можно а) не указывать тип возвращаемого значения; б) вместо for-yield-for-yield написать for {..;..} yield; в) вместо List(List.empty[A]) написать List(List[A]()); г) не писать последний toList; д) ну и наверно еще что-то.

update: А насчет эрланга я согласен с присутствующими - признаю, что на нем пишут серьезные вещи, но как можно их писать на языке с таким синтаксисом - не понимаю.

list comprehensions не являются интуитивно понятными

Для того, кто математику в жизни не изучал - конечно, не являются.

Спасибо, за ответы.

Простите, меня всё равно не могу разобраться.

Кто-нибудь, может показать полную подстановку, как будут получены первые три результата: 123, 132, 213.

Или описание словами.

Люди добрые, помогите.

Спасибо.

Ну ема. Perms возвращает что? -Все пермутации списка; запомнили.
Как это происходит:

1. для каждого элемента списка временно как-бы* изымаем его из списка
2. находим все пермутации остаточного списка (таким же способом)
3. цепляем изъятый элемент к началу каждой полученной пермутации
3.5 как-бы* возвращаем элемент обратно для следующей итерации
4. собственно профит

Собственно ходы:

123 = 1+(23) 2+(13) 3+(12) -- раскрой скобки по порядку
23 = 2+3 3+2
13 = 1+3 3+1
12 = 1+2 2+1

123 -> 123 132 213 231 312 321

Порядок вызова функции perms:

perms "123"
  perms "23"   -- h = 1
    perms "3"  -- h = 2
      perms "" -- h = 3
    perms "2"  -- h = 3
      perms "" -- h = 2
  perms "13"   -- h = 2
    perms "3"  -- h = 1
      perms "" -- h = 3
    perms "1"  -- h = 3
      perms "" -- h = 1
  perms "12"   -- h = 3
    perms "2"  -- h = 1
      perms "" -- h = 2
    perms "1"  -- h = 2
      perms "" -- h = 1

Просто там его оче мало.

Люди добрые.

Спасибо, разобрался.

L у меня принимало разные значения, вот и не складывалось.

L - же не меняется! ;)

Супер!

Всем огромное спасибо.

не указывать тип возвращаемого значения;

нельзя. Для рекурсивных функций нельзя.

не писать последний toList;

собственно тоже нельзя по той же причине. остальное ща попробую осилить. //кстати это похоже на задание с курсов Одерского, но я уже все забыл.

так гораздо лучше.

def perms_minimized[A](in:List[A]):List[List[A]]=
    in match{
      case a if a.isEmpty => List(List[A]())
      case _  => (for(x<-in; y<-perms_minimized(in.diff(List(x)))) yield x::y).toList
    }

еще бы чего тут улучшить

Люди с именем денис не готовы к компьютеру

Просто ты тупой.

Туп тот - кто пишет - что кто-то туп. Оскорблять людей - нехорошо и глупо.

Кто понимает свою тупость - мудр, а кто не понимает - глуп.

Анонимус, вы не знали этого?

Может быть вы не готовы к жизни?

Но теперь то вы знаете, и уже готовы.