February 18th, 2012

with Cat The Cat

List Rank (http://en.wikipedia.org/wiki/List_ranking).

Поражён элегантностью алгоритма:
{-# LANGUAGE ParallelListComp #-}

listRankWalk pt vs
	| nextPt == pt = [(pt,vs)]
	| otherwise = (pt,vs) : listRankWalk nextPt nextVs
	where
		nextPt = [pt !! i | i <- pt]
		nextVs = [v + nv | v <- vs | nv <- [vs !! i | i <- pt]]
listRank pt = listRankWalk pt vs
	where
		vs = [if i == j then 0 else 1 | i <- [0..] | j <- pt]
Индексы в "массиве" (у меня список для простоты) определяют положение следующего элемента в списке. Если номера равны, то это хвост. Например, [2,3,2,3] это два списка 0->2 и 1->3.

Вариант кода выше показывает шаги, совершённые агоритмом:
*Main> mapM_ print $ listRank [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15]
([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0])
([2,3,4,5,6,7,8,9,10,11,12,13,14,15,15,15],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,0])
([4,5,6,7,8,9,10,11,12,13,14,15,15,15,15,15],[4,4,4,4,4,4,4,4,4,4,4,4,3,2,1,0])
([8,9,10,11,12,13,14,15,15,15,15,15,15,15,15,15],[8,8,8,8,8,8,8,8,7,6,5,4,3,2,1,0])
([15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15],[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0])