How to count number of element occurrences in a list in Prolog

by

The following is based on my previous answer to “Remove duplicates in list (Prolog)” and on this previous answer to the question “Prolog union for A U B U C“.

list_item_subtracted_count0_count/5 is derived from list_item_subtracted/3.
list_counts/2 is derived from list_setB/2, which were both defined here.

list_item_subtracted_count0_count([], _, [], N,N).
list_item_subtracted_count0_count([A|As], E, Bs1, N0,N) :-
   if_(A = E,
       ( Bs1 =    Bs , N1 is N0+1 ), 
       ( Bs1 = [A|Bs], N1 =  N0   )),
   list_item_subtracted_count0_count(As, E, Bs, N1,N).

list_counts([], []).
list_counts([X|Xs], [X-N|Ys]) :-
   list_item_subtracted_count0_count(Xs, X, Xs0, 1,N),
   list_counts(Xs0, Ys).

Here’s the query the OP gave:

?- list_counts([c,c,a,a,b,b,d,a,c,b,d,d,a], Xss).
Xss = [c-3,a-4,b-3,d-3].                    % succeeds deterministically

Note the order of pairs X-N in Counts corresponds to the first occurrence of X in Xs:

?- list_counts([a,b,c,d], Xss).
Xss = [a-1,b-1,c-1,d-1].

?- list_counts([d,c,b,a], Xss).
Xss = [d-1,c-1,b-1,a-1].

Last, let’s consider all possible lists Es—enumerated fairly with ascending lengths:

?- length(Es, N), list_counts(Es, Xss).
   N = 0, Es = [],      Xss = []
;  N = 1, Es = [A],     Xss = [A-1]
;  N = 2, Es = [A,A],   Xss = [A-2]
;  N = 2, Es = [A,B],   Xss = [A-1,B-1],     dif(B,A)
;  N = 3, Es = [A,A,A], Xss = [A-3]
;  N = 3, Es = [A,A,B], Xss = [A-2,B-1],     dif(B,A)
;  N = 3, Es = [A,B,A], Xss = [A-2,B-1],     dif(B,A)
;  N = 3, Es = [B,A,A], Xss = [B-1,A-2],     dif(A,B), dif(A,B)
;  N = 3, Es = [A,B,C], Xss = [A-1,B-1,C-1], dif(C,A), dif(C,B), dif(B,A)
...

More Related Contents:

  1. prolog change show answer to print into list
  2. Prolog union for A U B U C
  3. Prolog – count repetitions in list
  4. Prolog removing unique elements only
  5. Find powers of 2 in a list Prolog
  6. Flatten a list in Prolog
  7. How do I append lists in Prolog?
  8. Prolog: Filtering a list?
  9. Remove duplicates in list (Prolog)
  10. Subsets in Prolog
  11. Get elements from list of lists
  12. Lazy lists in Prolog?
  13. Segregating Lists in Prolog
  14. Splitting a list of integers into a list of positive integers and a list of negative integers
  15. Intersection and union of 2 lists
  16. Prolog: First duplicate value
  17. Implementing “last” in Prolog
  18. Recursive Prolog predicate for reverse / palindrome
  19. Prolog, find minimum in a list
  20. Concatenating two lists – difference between ‘+=’ and extend()
  21. Test if lists share any items in python
  22. How to check if all of the following items are in a list?
  23. Get number of items from list (or other iterable) with certain condition
  24. How do I split or chunk a list into equal parts, with Dart?
  25. Difference between a Seq and a List in Scala
  26. XPath 1.0 to find if an element’s value is in a list of values
  27. How can I read the contents of a file into a list in Lisp?
  28. R: Print list to a text file
  29. Add or remove an entry from a List type attribute in a DynamoDB table item
  30. Splitting a list of items into two lists of odd and even indexed items

Leave a Comment