[Haskell] Получить все беспорядки [0..n] - Декларативное программирование

Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.

disorders n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])

А можно ли не фильтровать, а сразу строить только нужные перестановки?

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

H>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.
H>

H>disorders n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
H>

filter (/=[0..n]) (permutations [0..n])

H>А можно ли не фильтровать, а сразу строить только нужные перестановки?

disorders n = inserts n (disorders (n-1)) ++ dropLast (inserts n [0..n-1])

-- вставляет x во все возможные позиции списка xs
inserts x [] = [х]]
inserts x xs = (x:xs) : map (head xs

(inserts x (tail xs) )

dropLast = reverse.tail.reverse

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

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

H>>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.
H>>

H>>disorders n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
H>>

BZ>filter (/=[0..n]) (permutations [0..n])

Не, тут пролезают неполные беспорядки. Сравни

>let disorders'  n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
>let disorders'' n = filter (/= [0..n]) (permutations [0..n])
> disorders' 2
[[1,2,0],[2,0,1]]
> disorders'' 2
[[1,0,2],[2,1,0],[1,2,0],[2,0,1],[0,2,1]]

H>>А можно ли не фильтровать, а сразу строить только нужные перестановки?

BZ>disorders n = inserts n (disorders (n-1)) ++ dropLast (inserts n [0..n-1])

Типы слагаемых в ++ разные

BZ>-- вставляет x во все возможные позиции списка xs
BZ>inserts x [] = [х]]
BZ>inserts x xs = (x:xs) : map (head xs

(inserts x (tail xs) )

BZ>dropLast = reverse.tail.reverse

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

H>>>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.
BZ>>filter (/=[0..n]) (permutations [0..n])
D>Не, тут пролезают неполные беспорядки. Сравни
ага, я неправильно понял задачу

H>>>А можно ли не фильтровать, а сразу строить только нужные перестановки?

BZ>>disorders n = inserts n (disorders (n-1)) ++ dropLast (inserts n [0..n-1])

D>Типы слагаемых в ++ разные

ес-но, не [0..n-1], а n-1. в любом случае, это не то

значит, на первом месте может стоять кто угодно кроме 0, на втором — кто угодно из оставшихся кроме 1 и т.д.

H>disorders n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
H>

H>А можно ли не фильтровать, а сразу строить только нужные перестановки?

*Disorders> evalStateT (forM [1..4] $ \i -> do {xs <- get; x <- lift xs; guard $ x /= i; modify $ filter (x /=); return x}) [1..4]
[[2,1,4,3],[2,3,4,1],[2,4,1,3],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,3,1,2],[4,3,2,1]]

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

H>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.

Вот интересно... количество беспорядков N элементов — это, ЕМНИП, (N-1)!
Нельзя ли как-то исхитриться и родить беспорядки на основе перестановок N-1 элементов? (При условии, что МНИП, естественно).

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

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

H>>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.

К>Вот интересно... количество беспорядков N элементов — это, ЕМНИП, (N-1)!
К>Нельзя ли как-то исхитриться и родить беспорядки на основе перестановок N-1 элементов? (При условии, что МНИП, естественно).

И. Количество беспорядков N элементов = ближайшее целое к N!/e, то есть несколько больше (N-1)!

От:	hexamino	http://hexamino.blogspot.com/
Дата:	15.10.09 14:39
Оценка:

	От:	BulatZiganshin
	Дата:	15.10.09 16:59
	Оценка:

	От:	deniok
	Дата:	15.10.09 18:33
	Оценка:

	От:	BulatZiganshin
	Дата:	15.10.09 18:51
	Оценка:

От:	MigMit	http://migmit.vox.com
Дата:	15.10.09 21:30
Оценка:

	От:	Кодт
	Дата:	19.10.09 01:41
	Оценка: