2

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.

Knoothe
  • 1,218
  • 8
  • 14
Daniyal Javani
  • 229
  • 1
  • 5
  • 10
  • With 100 digits, there are 5050 subsequences. Do you really want all of them? – John Dvorak Mar 23 '13 at 06:44
  • So, now nested loops to print sequence have a fancy name **algorithm**. – phoeagon Mar 23 '13 at 15:37
  • @JanDvorak [1,3] subsequence isn't include for this algorithm. so 100 digits has 200 subsequence! –  Sep 06 '14 at 17:12
  • @KasiyA indeed. That would be 2^1024 subsequences, a number far bigger than 5050, barely fitting into this comment field (not the box itself), hard to transcribe manually, and definitely not worth reading. – John Dvorak Sep 06 '14 at 17:13
  • @JanDvorak with `[1,2,3,4,5,6]` we have this sub `[1] [2] [3] [4] [5] [6] [1,2] [2,3] [3,4] [4,5] [5,6] [1,2,3,4,5,6]`. n*2 subsequences. –  Sep 06 '14 at 17:16

3 Answers3

1

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);

}
siddstuff
  • 1,215
  • 4
  • 16
  • 37
0

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.

Community
  • 1
  • 1
Chasefornone
  • 747
  • 1
  • 7
  • 15
0

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?.

Community
  • 1
  • 1
jfs
  • 399,953
  • 195
  • 994
  • 1,670
  • 1
    Note that [1,3] is not part of the sample output. The question is not clear, I presumed it to be subarrays, added an answer, and deleted it later when I got no response from OP. Perhaps your answer is what they want, and the [1,3] is just an omission. – Knoothe Mar 25 '13 at 04:36
  • @Knoothe: you're right. The OP might be asking about [subarrays](http://ideone.com/SIX9jU) as in [your answer](http://stackoverflow.com/a/15584292/4279), not subsequences in general. – jfs Mar 25 '13 at 12:59
  • [1,3] not include in question output. the question said 6 sub for [1,2.3] but you have 7 sub –  Sep 06 '14 at 17:19