CODEWITHSUNDEEP
algorithmsequence
Daniyal Javani
Daniyal Javani

Reputation: 235

Algorithm to find a sequence of sub-sequences

Sequence [1,2,3] consider. This sequence has the following 6 different sequence: [1]and [2]and [3] and [1,2] and [2,3] and [1,2,3]

Note! Length the initial sequence may be up to 100 digits. Please help me. How can I make the following sequences? I love researching more about this kind of algorithms. Please tell me the name of this type of algorithms.

Upvotes: 2

Views: 587

Answers (3)

jfs
jfs

Reputation: 414179

It is called a power set (in your case the empty set is excluded).

To build a power set, start with a set with an empty set in it; then for each item in the input set extend the power set with all its subsets accumulated so far with the current item included (in Python):

def powerset(lst):
    S = [[]]
    for item in lst:
        S += [subset + [item] for subset in S]
    return S

Example:

print(powerset([1, 2, 3]))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

To avoid producing all subsets at once, a recursive definition could be used:

  • a power set of an empty set is a set with an empty set in it
  • a power set of a set with n items contains all subsets from a power set of a set with n - 1 items plus all these subsets with the n-th item included.
def ipowerset(lst):
    if not lst: # empty list
        yield []
    else:
        item, *rest = lst
        for subset in ipowerset(rest):
            yield subset
            yield [item] + subset

Example:

print(list(ipowerset([1, 2, 3])))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Yet another way to generate a power set is to generate r-length subsequences (combinations) for all r from zero to the size of the input set (itertools recipe):

from itertools import chain, combinations

def powerset_comb(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Example:

print(list(powerset_comb([1, 2, 3])))
# -> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]

See also what's a good way to combinate through a set?.

Upvotes: 0

Chasefornone
Chasefornone

Reputation: 757

Your problem can be reduced to the Combination problem. There are already many solutions existed in stackoverflow. You can check this, it may be useful for you.

Upvotes: 0

siddstuff
siddstuff

Reputation: 1255

Here is a c code to print all sub sequences. Algorithm uses nested loops.

    #include<stdio.h>

  void seq_print(int A[],int n)
{
    int k;
    for(int i =0;i<=n-1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            k=j;
            while(k<=i)
            {
                printf("%d",A[k]);
                k++;

            }
            printf("\n");
        }
}

}

void main()
{
    int A[]={1,2,3,4,5,6,7,8,9,0};
    int n=10;
    seq_print(A,n);

}

Upvotes: 1

Related Questions