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

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

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 2 мес. назад.

  • Автор
    Сообщения
  • #2621

    questioner
    Участник

    Здравствуйте. Есть задача, решить нужно на Visual Prolog:

    по исходному списку целых чисел создать описание мультимножества в виде списка пар, в которых первая компонента — элемент множества, а вторая — его количество в исходном списке

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

  • #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).

Для ответа в этой теме необходимо авторизоваться.