Ответ в теме: Создать мультимножество из списка

      Комментарии к записи Ответ в теме: Создать мультимножество из списка отключены
#2622

Я думаю, что вариант решения с построением множества, а затем – подсчетом числа вхождений его элементов – наиболее правильный, т.к. в любом случае асимптотическая сложность алгоритма будет O(n), но это будет более чистый код с точки зрения возможностей повторного использования и простоты внесения изменений.

Если же все-таки нужен другой вариант решения, то можно постепенно отделять от исходного списка элементы и складывать их в буфер (аккумулятор) по принципу накапливающего параметра, руководствуясь правилами:

  1. если элемент уже есть в буфере – то он пропускается (сразу переходим к обработке остальных);
  2. если элемента еще нет в буфере – подсчитаем для него число вхождений в списке и добавим пару в буфер

Для подсчета числа вхождений элемента можно использовать функцию count. Для проверки наличия элемента в списке можно использовать как функцию member, так и использовать count с инициализированным нулем значением количества вхождений:

domains
	element = integer
	list = element*
	counter = integer
	pair_list_element = pair(element, counter)
	pair_list = pair_list_element*
predicates
	list_to_multiset(list, pair_list)
	list_to_multiset_accumulator(list, pair_list, pair_list)
clauses
	list_to_multiset(List, PairList):-
		list_to_multiset_accumulator(List, [], PairList).

	list_to_multiset_accumulator([], Accumulator, Accumulator):-!.
	list_to_multiset_accumulator([Head|Tail], Accumulator, PairList):-
	    % if no such element in accumulator:
		count(pair(Head, _Counter), Accumulator, 0), !, 
		count(Head, [Head|Tail], Counter), 
		list_to_multiset_accumulator(Tail, [pair(Head, Counter)|Accumulator], PairList).
	list_to_multiset_accumulator([_Head|Tail], Accumulator, PairList):-
		% if Head element included in Accumulator:
		list_to_multiset_accumulator(Tail, Accumulator, PairList). % process Tail
goal
	List = [1,2,3,2,3,4,5,4,3,4,5,6,4,3,2,3],
	list_to_multiset_accumulator(List, PairList).