| Did you know ... | Search Documentation: |
 | Pack logtalk -- logtalk-3.98.0/docs/apis/_sources/subsequences_protocol_0.rst.txt |
- HOME
- DOWNLOAD
- DOCUMENTATION
- TUTORIALS
- Beginner▶
- Advanced▶
- Web applications▶
- Semantic web▶
- Graphics▶
- Machine learning▶
- External collections▶
- For packagers▶
- COMMUNITY
- COMMERCIAL
- WIKI
.. index:: single: subsequences_protocol .. _subsequences_protocol/0:
.. rst-class:: right
protocol
subsequences_protocol
Protocol for subsequence operations over lists.
| Availability:
| logtalk_load(subsequences(loader))
| Author: Paulo Moura | Version: 1:0:0 | Date: 2026-02-26
| Compilation flags:
| static
| Dependencies: | (none)
| Remarks:
- Generation operations: Predicates for generating all subsequences or variants thereof.
- Ordering variants: Predicates that support an additional Order argument (default, lexicographic, or shortlex) for controlling output order.
- Searching and matching: Predicates for finding specific subsequences with desired properties.
- Prefix and suffix operations: Predicates for checking and finding prefixes and suffixes.
- Contiguous subsequences: Predicates for working with contiguous subsequences (subslices, sliding windows).
- Random selection: Predicates for randomly selecting subsequences.
- Constrained operations: Predicates for generating subsequences with specific constraints.
- Utility predicates: Helper predicates for subsequence operations.
| Inherited public predicates: | (none)
.. contents:: :local: :backlinks: top
Public predicates
.. index:: subsequences/2 .. _subsequences_protocol/0::subsequences/2:
subsequences/2 ^^^^^^^^^^^^^^^^^^
Generates all subsequences of a list using default order. A subsequence maintains the relative order of elements but need not be contiguous. The empty list is included.
| Compilation flags:
| static
| Template:
| subsequences(List,Subsequences)
| Mode and number of proofs:
| subsequences(+list,-list) - one
| Examples:
| All subsequences
| subsequences([a,b,c],Subsequences)
| Subsequences=[[],[a],[b],[a,b],[c],[a,c],[b,c],[a,b,c]]
.. index:: subsequence/2 .. _subsequences_protocol/0::subsequence/2:
subsequence/2 ^^^^^^^^^^^^^^^^^
True iff the second argument is a subsequence of the first argument. Subsequences of a list using default order. A subsequence maintains the relative order of elements but need not be contiguous. The empty list is included.
| Compilation flags:
| static
| Template:
| subsequence(List,Subsequence)
| Mode and number of proofs:
| subsequence(+list,-list) - one_or_more
| Examples:
| A subsequence
| subsequence([1,2],Subsequence)
| Subsequence=[]
.. index:: subsequences/3 .. _subsequences_protocol/0::subsequences/3:
subsequences/3 ^^^^^^^^^^^^^^^^^^
Generates all subsequences of a list with specified ordering: default (as naturally produced), lexicographic, or shortlex (by length first, then lexicographically).
| Compilation flags:
| static
| Template:
| subsequences(List,Order,Subsequences)
| Mode and number of proofs:
| subsequences(+list,+atom,-list) - one
| Examples:
| Shortlex order
| subsequences([a,b],shortlex,Subsequences)
| Subsequences=[[],[a],[b],[a,b]]
.. index:: subsequence/3 .. _subsequences_protocol/0::subsequence/3:
subsequence/3 ^^^^^^^^^^^^^^^^^
True iff the third argument is a subsequence of the first argument with specified ordering: default (as naturally produced), lexicographic, or shortlex (by length first, then lexicographically).
| Compilation flags:
| static
| Template:
| subsequence(List,Order,Subsequence)
| Mode and number of proofs:
| subsequence(+list,+atom,-list) - one_or_more
| Examples:
| Shortlex order
| subsequence([a,b],shortlex,Subsequence)
| Subsequence=[]
.. index:: nonempty_subsequences/2 .. _subsequences_protocol/0::nonempty_subsequences/2:
nonempty_subsequences/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Generates all non-empty subsequences of a list.
| Compilation flags:
| static
| Template:
| nonempty_subsequences(List,Subsequences)
| Mode and number of proofs:
| nonempty_subsequences(+list,-list) - one
| Examples:
| Non-empty subsequences
| nonempty_subsequences([a,b],Subsequences)
| Subsequences=[[a],[b],[a,b]]
.. index:: nonempty_subsequence/2 .. _subsequences_protocol/0::nonempty_subsequence/2:
nonempty_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^
True iff the second argument is a non-empty subsequence of the first argument.
| Compilation flags:
| static
| Template:
| nonempty_subsequence(List,Subsequence)
| Mode and number of proofs:
| nonempty_subsequence(+list,-list) - one_or_more
| Examples:
| Non-empty subsequence
| nonempty_subsequence([a,b],Subsequence)
| Subsequence=[a]
.. index:: power_set/2 .. _subsequences_protocol/0::power_set/2:
power_set/2 ^^^^^^^^^^^^^^^
Generates the power set of a list (all possible subsequences). Alias for subsequences/2 when first argument is ground.
| Compilation flags:
| static
| Template:
| power_set(List,PowerSet)
| Mode and number of proofs:
| power_set(+list,-list) - one
| Examples:
| Power set
| power_set([a,b],PowerSet)
| PowerSet=[[],[a],[b],[a,b]]
.. index:: inits/2 .. _subsequences_protocol/0::inits/2:
inits/2 ^^^^^^^^^^^
Generates all initial segments (prefixes) of a list, shortest first. Includes the empty list.
| Compilation flags:
| static
| Template:
| inits(List,Inits)
| Mode and number of proofs:
| inits(+list,-list) - one
| Examples:
| All prefixes
| inits([a,b,c],Inits)
| Inits=[[],[a],[a,b],[a,b,c]]
.. index:: init/2 .. _subsequences_protocol/0::init/2:
init/2 ^^^^^^^^^^
True iff the second argument is one of the initial segments (prefixes) of a list.
| Compilation flags:
| static
| Template:
| init(List,Inits)
| Mode and number of proofs:
| init(+list,-term) - zero_or_more
| init(+list,+term) - zero_or_one
| Examples:
| Check prefix
| init([a,b,c],[a,b])
| true
.. index:: tails/2 .. _subsequences_protocol/0::tails/2:
tails/2 ^^^^^^^^^^^
Generates all final segments (suffixes) of a list, longest first. Includes the empty list.
| Compilation flags:
| static
| Template:
| tails(List,Tails)
| Mode and number of proofs:
| tails(+list,-list) - one
| Examples:
| All suffixes
| tails([a,b,c],Tails)
| Tails=[[a,b,c],[b,c],[c],[]]
.. index:: tail/2 .. _subsequences_protocol/0::tail/2:
tail/2 ^^^^^^^^^^
True iff the second argument is one of the final segments (suffixes) of a list.
| Compilation flags:
| static
| Template:
| tail(List,Tails)
| Mode and number of proofs:
| tail(+list,-term) - zero_or_more
| tail(+list,+term) - zero_or_one
| Examples:
| Check suffix
| tail([a,b,c],[b,c])
| true
.. index:: inits1/2 .. _subsequences_protocol/0::inits1/2:
inits1/2 ^^^^^^^^^^^^
Generates all non-empty initial segments (prefixes) of a list, shortest first.
| Compilation flags:
| static
| Template:
| inits1(List,Inits)
| Mode and number of proofs:
| inits1(+list,-list) - one
| Examples:
| Non-empty prefixes
| inits1([a,b,c],Inits)
| Inits=[[a],[a,b],[a,b,c]]
.. index:: init1/2 .. _subsequences_protocol/0::init1/2:
init1/2 ^^^^^^^^^^^
True iff the second argument is a non-empty initial segment (prefix) of a list, shortest first.
| Compilation flags:
| static
| Template:
| init1(List,Init)
| Mode and number of proofs:
| init1(+list,-term) - one_or_more
| Examples:
| Non-empty prefix
| init1([a,b,c],Init)
| Init=[a]
.. index:: tails1/2 .. _subsequences_protocol/0::tails1/2:
tails1/2 ^^^^^^^^^^^^
Generates all non-empty final segments (suffixes) of a list, longest first.
| Compilation flags:
| static
| Template:
| tails1(List,Tails)
| Mode and number of proofs:
| tails1(+list,-list) - one
| Examples:
| Non-empty suffix
| tails1([a,b,c],Tails)
| Tails=[[a,b,c],[b,c],[c]]
.. index:: tail1/2 .. _subsequences_protocol/0::tail1/2:
tail1/2 ^^^^^^^^^^^
True iff the second argument is a non-empty final segment (suffix) of a list, longest first.
| Compilation flags:
| static
| Template:
| tail1(List,Tail)
| Mode and number of proofs:
| tail1(+list,-list) - one
| Examples:
| Non-empty suffix
| tail1([a,b,c],Tail)
| Tail=[a,b,c]
.. index:: init_tails/2 .. _subsequences_protocol/0::init_tails/2:
init_tails/2 ^^^^^^^^^^^^^^^^
Generates all pairs of initial and final segments. Each pair Init-Tail represents a split of the list where Init+Tail equals the original list. When the second argument is bound, checks if it is a valid split.
| Compilation flags:
| static
| Template:
| init_tails(List,InitTailPairs)
| Mode and number of proofs:
| init_tails(+list,-list) - one
| Examples:
| All splits
| init_tails([a,b],InitTailPairs)
| InitTailPairs=['-'([],[a,b]),'-'([a],[b]),'-'([a,b],[])]
.. index:: init_tail/2 .. _subsequences_protocol/0::init_tail/2:
init_tail/2 ^^^^^^^^^^^^^^^
True iff (Init,Tail) represents a split of the list where Init+Tail equals the original list.
| Compilation flags:
| static
| Template:
| init_tail(List,InitTailPairs)
| Mode and number of proofs:
| init_tail(+list,-term) - one_or_more
| Examples:
| Check split
| init_tail([a,b,c],'-'([a],[b,c]))
| true
.. index:: longest_common_subsequence/3 .. _subsequences_protocol/0::longest_common_subsequence/3:
longest_common_subsequence/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Finds the longest common subsequence (LCS) between two lists. Uses dynamic programming.
| Compilation flags:
| static
| Template:
| longest_common_subsequence(List1,List2,LCS)
| Mode and number of proofs:
| longest_common_subsequence(+list,+list,-list) - one
| Examples:
| LCS example
| longest_common_subsequence([a,b,c,d,e],[a,c,e,f],LCS)
| LCS=[a,c,e]
.. index:: longest_increasing_subsequence/2 .. _subsequences_protocol/0::longest_increasing_subsequence/2:
longest_increasing_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Finds the longest strictly increasing subsequence in a list. Elements must be comparable.
| Compilation flags:
| static
| Template:
| longest_increasing_subsequence(List,LIS)
| Mode and number of proofs:
| longest_increasing_subsequence(+list,-list) - one
| Examples:
| LIS example
| longest_increasing_subsequence([3,1,4,1,5,9,2,6],LIS)
| LIS=[1,4,5,9]
.. index:: longest_decreasing_subsequence/2 .. _subsequences_protocol/0::longest_decreasing_subsequence/2:
longest_decreasing_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Finds the longest strictly decreasing subsequence in a list. Elements must be comparable.
| Compilation flags:
| static
| Template:
| longest_decreasing_subsequence(List,LDS)
| Mode and number of proofs:
| longest_decreasing_subsequence(+list,-list) - one
| Examples:
| LDS example
| longest_decreasing_subsequence([9,5,2,8,3,1],LDS)
| LDS=[9,5,2,1]
.. index:: longest_common_increasing_subsequence/3 .. _subsequences_protocol/0::longest_common_increasing_subsequence/3:
longest_common_increasing_subsequence/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Finds the longest subsequence that is both common to two lists and strictly increasing.
| Compilation flags:
| static
| Template:
| longest_common_increasing_subsequence(List1,List2,LCIS)
| Mode and number of proofs:
| longest_common_increasing_subsequence(+list,+list,-list) - one
| Examples:
| LCIS example
| longest_common_increasing_subsequence([1,4,2,5],[4,1,3,5],LCIS)
| LCIS=[1,5]
.. index:: longest_repeating_subsequence/2 .. _subsequences_protocol/0::longest_repeating_subsequence/2:
longest_repeating_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Finds the longest subsequence that appears at least twice in the list (at different positions).
| Compilation flags:
| static
| Template:
| longest_repeating_subsequence(List,LRS)
| Mode and number of proofs:
| longest_repeating_subsequence(+list,-list) - one
| Examples:
| LRS example
| longest_repeating_subsequence([a,a,b,a,b],LRS)
| LRS=[a,b]
.. index:: is_subsequence_of/2 .. _subsequences_protocol/0::is_subsequence_of/2:
is_subsequence_of/2 ^^^^^^^^^^^^^^^^^^^^^^^
Checks if the first list is a subsequence of the second list. All elements must occur in order.
| Compilation flags:
| static
| Template:
| is_subsequence_of(Subsequence,List)
| Mode and number of proofs:
| is_subsequence_of(+list,+list) - zero_or_one
| Examples:
| Valid subsequence
| is_subsequence_of([a,c],[a,b,c])
| true
| Invalid subsequence
| is_subsequence_of([c,a],[a,b,c])
| false
.. index:: proper_subsequence/2 .. _subsequences_protocol/0::proper_subsequence/2:
proper_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^
Checks if the first list is a proper subsequence of the second list (i.e., subsequence and not equal).
| Compilation flags:
| static
| Template:
| proper_subsequence(Subsequence,List)
| Mode and number of proofs:
| proper_subsequence(+list,+list) - zero_or_one
| Examples:
| Proper subsequence
| proper_subsequence([a,c],[a,b,c])
| true
| Not proper (equal lists)
| proper_subsequence([a,b,c],[a,b,c])
| false
.. index:: subsequence_at_indices/3 .. _subsequences_protocol/0::subsequence_at_indices/3:
subsequence_at_indices/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Extracts a subsequence using a strictly increasing list of 1-based indices.
| Compilation flags:
| static
| Template:
| subsequence_at_indices(List,Indices,Subsequence)
| Mode and number of proofs:
| subsequence_at_indices(+list,+list,-list) - zero_or_one
| Examples:
| Indices selection
| subsequence_at_indices([a,b,c,d],[1,3],Subsequence)
| Subsequence=[a,c]
.. index:: common_subsequences/3 .. _subsequences_protocol/0::common_subsequences/3:
common_subsequences/3 ^^^^^^^^^^^^^^^^^^^^^^^^^
Generates all subsequences that are common to both lists.
| Compilation flags:
| static
| Template:
| common_subsequences(List1,List2,CommonSubsequences)
| Mode and number of proofs:
| common_subsequences(+list,+list,-list) - one
| Examples:
| All common subsequences
| common_subsequences([a,b,c],[a,c,d],CommonSubsequences)
| CommonSubsequences=[[a,c],[a],[c],[]]
.. index:: common_subsequence/3 .. _subsequences_protocol/0::common_subsequence/3:
common_subsequence/3 ^^^^^^^^^^^^^^^^^^^^^^^^
True iff the third argument is a common subsequence of both lists.
| Compilation flags:
| static
| Template:
| common_subsequence(List1,List2,CommonSubsequence)
| Mode and number of proofs:
| common_subsequence(+list,+list,-list) - one_or_more
| Examples:
| Check common subsequence
| common_subsequence([a,b,c],[a,c,d],[a,c])
| true
.. index:: count_distinct_subsequences/3 .. _subsequences_protocol/0::count_distinct_subsequences/3:
count_distinct_subsequences/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Counts the number of distinct occurrences of a pattern as a subsequence in a list.
| Compilation flags:
| static
| Template:
| count_distinct_subsequences(Pattern,List,Count)
| Mode and number of proofs:
| count_distinct_subsequences(+list,+list,-integer) - one
| Examples:
| Count occurrences
| count_distinct_subsequences([a,b],[a,a,b,b],Count)
| Count=4
.. index:: is_prefix_of/2 .. _subsequences_protocol/0::is_prefix_of/2:
is_prefix_of/2 ^^^^^^^^^^^^^^^^^^
Checks if the first list is a prefix of the second list.
| Compilation flags:
| static
| Template:
| is_prefix_of(Prefix,List)
| Mode and number of proofs:
| is_prefix_of(+list,+list) - zero_or_one
| Examples:
| Valid prefix
| is_prefix_of([a,b],[a,b,c])
| true
| Invalid prefix
| is_prefix_of([b,c],[a,b,c])
| false
.. index:: is_suffix_of/2 .. _subsequences_protocol/0::is_suffix_of/2:
is_suffix_of/2 ^^^^^^^^^^^^^^^^^^
Checks if the first list is a suffix of the second list.
| Compilation flags:
| static
| Template:
| is_suffix_of(Suffix,List)
| Mode and number of proofs:
| is_suffix_of(+list,+list) - zero_or_one
| Examples:
| Valid suffix
| is_suffix_of([b,c],[a,b,c])
| true
| Invalid suffix
| is_suffix_of([a,b],[a,b,c])
| false
.. index:: subslices/2 .. _subsequences_protocol/0::subslices/2:
subslices/2 ^^^^^^^^^^^^^^^
Generates all contiguous non-empty subslices (sublists) of a list.
| Compilation flags:
| static
| Template:
| subslices(List,Subslice)
| Mode and number of proofs:
| subslices(+list,-list) - one
| subslices(+list,?list) - zero_or_more
| Examples:
| All subslices
| subslices([a,b,c],Subslice)
| Subslice=[[a],[a,b],[a,b,c],[b],[b,c],[c]]
.. index:: sliding_window/3 .. _subsequences_protocol/0::sliding_window/3:
sliding_window/3 ^^^^^^^^^^^^^^^^^^^^
Generates all contiguous windows of size N from a list. Fails if N is larger than the list length.
| Compilation flags:
| static
| Template:
| sliding_window(N,List,Window)
| Mode and number of proofs:
| sliding_window(+integer,+list,-list) - one
| sliding_window(+integer,+list,?list) - zero_or_more
| Examples:
| Windows of size 2
| sliding_window(2,[a,b,c,d],Window)
| Window=[[a,b],[b,c],[c,d]]
.. index:: random_subsequence/2 .. _subsequences_protocol/0::random_subsequence/2:
random_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^
Randomly selects one subsequence uniformly from all 2^N possible subsequences.
| Compilation flags:
| static
| Template:
| random_subsequence(List,Subsequence)
| Mode and number of proofs:
| random_subsequence(+list,-list) - one
| Examples:
| Random subsequence
| random_subsequence([a,b,c],Subsequence)
| Subsequence=[a,c]
.. index:: subsequences_with_min_span/3 .. _subsequences_protocol/0::subsequences_with_min_span/3:
subsequences_with_min_span/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Generates subsequences where consecutive elements are at least MinSpan positions apart in the original list.
| Compilation flags:
| static
| Template:
| subsequences_with_min_span(MinSpan,List,Subsequence)
| Mode and number of proofs:
| subsequences_with_min_span(+integer,+list,-list) - one
| subsequences_with_min_span(+integer,+list,?list) - zero_or_more
| Examples:
| Min span of 2
| subsequences_with_min_span(2,[a,b,c,d],Subsequence)
| Subsequence=[a,c]
.. index:: alternating_subsequences/2 .. _subsequences_protocol/0::alternating_subsequences/2:
alternating_subsequences/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Generates all subsequences that alternate between increasing and decreasing (or vice versa). Elements must be comparable.
| Compilation flags:
| static
| Template:
| alternating_subsequences(List,AlternatingSubsequences)
| Mode and number of proofs:
| alternating_subsequences(+list,-list) - one
| Examples:
| All alternating subsequences
| alternating_subsequences([1,3,2,4],AlternatingSubsequences)
| AlternatingSubsequences=[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
.. index:: alternating_subsequence/2 .. _subsequences_protocol/0::alternating_subsequence/2:
alternating_subsequence/2 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
True iff the second argument is a subsequence that alternates between increasing and decreasing (or vice versa). Elements must be comparable.
| Compilation flags:
| static
| Template:
| alternating_subsequence(List,AlternatingSubsequence)
| Mode and number of proofs:
| alternating_subsequence(+list,-list) - one_or_more
| Examples:
| Alternating
| alternating_subsequence([1,3,2,4],AlternatingSubsequence)
| AlternatingSubsequence=[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
.. index:: k_distinct_subsequences/3 .. _subsequences_protocol/0::k_distinct_subsequences/3:
k_distinct_subsequences/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Generates all K-element subsequences where all elements are distinct (no duplicates in the subsequence itself).
| Compilation flags:
| static
| Template:
| k_distinct_subsequences(K,List,DistinctSubsequences)
| Mode and number of proofs:
| k_distinct_subsequences(+integer,+list,-list) - one
| Examples:
| All distinct only
| k_distinct_subsequences(2,[a,a,b],DistinctSubsequences)
| DistinctSubsequences=[[a,b],[a,c],[b,c]]
.. index:: k_distinct_subsequence/3 .. _subsequences_protocol/0::k_distinct_subsequence/3:
k_distinct_subsequence/3 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
True iff the third argument is a subsequence of the first argument that is a K-element subsequence where all elements are distinct (no duplicates in the subsequence itself).
| Compilation flags:
| static
| Template:
| k_distinct_subsequence(K,List,DistinctSubsequence)
| Mode and number of proofs:
| k_distinct_subsequence(+integer,+list,-list) - one
| Examples:
| A distinct only
| k_distinct_subsequence(2,[a,a,b],DistinctSubsequence)
| DistinctSubsequence=[a,b]
.. index:: count_subsequences/2 .. _subsequences_protocol/0::count_subsequences/2:
count_subsequences/2 ^^^^^^^^^^^^^^^^^^^^^^^^
Counts the total number of subsequences (always 2^N for a list of length N).
| Compilation flags:
| static
| Template:
| count_subsequences(List,Count)
| Mode and number of proofs:
| count_subsequences(+list,-integer) - one
| Examples:
| Count
| count_subsequences([a,b,c],Count)
| Count=8
.. index:: subsequence_length/2 .. _subsequences_protocol/0::subsequence_length/2:
subsequence_length/2 ^^^^^^^^^^^^^^^^^^^^^^^^
Returns the length of a subsequence (same as list length, provided for consistency).
| Compilation flags:
| static
| Template:
| subsequence_length(Subsequence,Length)
| Mode and number of proofs:
| subsequence_length(+list,-integer) - one
| Examples:
| Length
| subsequence_length([a,b,c],Length)
| Length=3
Protected predicates
(none)
Private predicates
(none)
Operators
(none)