Lazy Cjow Rhrr ([info]_lcr_) wrote,
@ 2006-05-15 11:40:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Current mood: creative
Entry tags:erlang

Рекурсивный перебор k-подмножеств
(Уфф, эти срочные проекты вышибли из колеи больше чем на месяц).

Хочу наконец закончить эстетствовать с перебором k-элементных подмножеств. Задачу сформулирую в наиболее общем виде: дан список (чего угодно), сформировать список всех его k-элементных подсписков.

start() ->
	comb([], [a,b,c,d,e,f], 3).

% comb([], [a,b,c,d,e,f], 3) ->
%	comb([a], [b,c,d,e,f], 2) ++
%	comb([b], [c,d,e,f], 2) ++
%	comb([c], [d,e,f], 2) ++
%	comb([d], [e,f], 2).	
comb(B, E, 1) ->
	Cons = fun (X) -> B ++ [X] end,
	map(Cons, E);
comb(B, E, K) when K == length(E) ->
	[B ++ E];
comb(B, E, K) ->
	combr(B, E, K-1).

combr(_B, E, K) when K == length(E) ->
	[];
combr(B, [EH|ET], K) ->
	%io:format("~w; ~w; ~w~n", [B ++ [hd(E)], tl(E), K]),
	comb(B ++ [EH], ET, K) ++ combr(B, ET, K).

Здесь текущее множество формируется из начала B и некоторого куска длины K из списка-конца E. В граничных условиях (когда нужно перебрать все 1-элементные подмножества, или E-элементные подмножества из E) задача решается непосредственным перебором, а в общем случае - рекурсивно. Красивое, компактное, хоть и не самое эффективное решение.
2> comb:start().
[[a,b,c],
 [a,b,d],
 [a,b,e],
 [a,b,f],
 [a,c,d],
 [a,c,e],
 [a,c,f],
 [a,d,e],
 [a,d,f],
 [a,e,f],
 [b,c,d],
 [b,c,e],
 [b,c,f],
 [b,d,e],
 [b,d,f],
 [b,e,f],
 [c,d,e],
 [c,d,f],
 [c,e,f],
 [d,e,f]]

Пока всё на этом.

Advertisement

(Post a new comment)


[info]lomeo
2006-05-15 08:11 am UTC (link)
Вот нарисовал на Хаскеле:
import List

comb [] _ = []
comb xs 1 = map return xs
comb xs n = concatMap comb' $ init $ tails xs
    where comb' (y:ys) = map (y:) (comb ys (n-1))


(Reply to this)(Thread)

[info]_lcr_
2006-05-27 12:27 pm UTC (link)
// извини за задержку с ответом - у меня всё плохо :-)
// теперь по теме

Хаскель великолепен, я впечатлён!

Ты меня заставил просто (косвенно, продемонстрировав весьма симпатичный вариант) разобраться в этом коде, но я попух на этом:
concatMap comb' $ init $ tails xs


Что такое tails xs? Допустимо ли переписать как
concat(map comb' (init (tails xs))

?

(Reply to this)(Parent)(Thread)

[info]lomeo
2006-05-27 06:24 pm UTC (link)
допустимо, оператор ($) определен как

f $ x = f x

но из-за того, что он имеет самый низкий приоритет, он используется для замены скобок.

tails возвращает все хвосты списка:

> tails [1,2,3]
[[1,2,3],[2,3],[3],[]]

(Reply to this)(Parent)(Thread)

[info]_lcr_
2006-05-29 08:04 am UTC (link)
допустимо, оператор ($) определен как
f $ x = f x
но из-за того, что он имеет самый низкий приоритет, он используется для замены скобок.

А точка (композиция, ".") чем тогда отличается?
-- concatMap = concat . map

И второй маленький вопрос: tails возвращает в том числе и пустой список. А init должен принимать в качестве аргумента непустой, поэтому на мой дилетанский взгляд возникнет исключение. Где я не прав?

пс: ориентировался на http://www.cs.uu.nl/~afie/haskell/tourofprelude.html

(Reply to this)(Parent)(Thread)

(Anonymous)
2006-05-29 08:21 am UTC (link)
1. Композиция же над функциями работает:
f . g = \x -> f (g x)
А здесь ($) мы простое применение аргумента к функции разбили.

Т.е. concat $ map нельзя, потому что у concat аргумент список должен быть, а не функция. Погляди на типы для ($) и (.) и поймешь.

2. Не так, tails возвращает НЕПУСТОЙ список, а то, что одним из его элементов является пустой список - в данном случае (для init) неважно. xs у нас заведомо не пустой, значит и tails вернет непустой список - [[]] - это список, состоящий из одного элемента - пустого списка.

(Reply to this)(Parent)(Thread)

[info]lomeo
2006-05-29 08:22 am UTC (link)
Упс, это я был.

(Reply to this)(Parent)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…