CODEWITHSUNDEEP
algorithm
JeanClaudeDaudin
JeanClaudeDaudin

Reputation: 435

all integers which are subsequences of an integer (considered as a string of digits)

Given an integer 1<=n<=100000. How do I get efficiently all the integers which are subsequences of the integer n (considering the integer n as a string of digits). I want a pseudo code for this.

eg. input: n=121, output: 1,12,11,2,21 (the order of output has no importance)

eg. input: n=132, output: 1,13,12,3,32,2

thanks in advance

Upvotes: 3

Views: 669

Answers (3)

Ayush
Ayush

Reputation: 2608

n=121

length = 3

Generate all possible binary numbers of length 3. See the set bits in binary number and print the corresponding digit from the original number.

Example 1

121   length=3

000  -> 0    (ignore this:no bit set)
001  -> 1    (__1)
010  -> 2    (_2_)
011  -> 21   (_21)
100  -> 1    (repeated: ignore this)
101  -> 11   (1_1)
110  -> 12   (12_)
111  -> 121  (121)

Example 2: n=1234

1234  length=4

0000  -> 0    (ignore this:no bit set)
0001  -> 4    (___4)
0010  -> 3    (__3_)
0011  -> 34   (__34)
0100  -> 2    (_2__)
0101  -> 24   (_2_4)
0110  -> 23   (_23_)
0111  -> 234  (_234)
1000  -> 1    (1___)
1001  -> 14   (1__4)
1010  -> 13   (1_3_)
1011  -> 134  (1_34)
1100  -> 12   (12__)
1101  -> 124  (12_4)
1110  -> 123  (123_)
1111  -> 1234 (1234)

The code for the above algorithm made by me in C is pasted below. I have not performed many optimizations but the logic is same.

Sorry for the unoptimized code.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define SIZE 30
main()
{
    int i,j,end,index,k,swap;
    char str[SIZE],arr[SIZE];
    char buffer[SIZE],dict[SIZE][SIZE]={'\0'};  //dictlength is used to store the 
    int dictlength=0;
    gets(str);
    for(i=1;i<pow(2,strlen(str));i++)
    {
        index=0;
        end=strlen(str);
        itoa(i,arr,2);
        for(j=strlen(arr);j>=0;j--,end--)
        {
            if(arr[j]=='1')
            {
                buffer[index]=str[end];
                index=index+1;
            }
        }
        buffer[index]='\0';
        for(k=0,j=strlen(buffer)-1; k<j ; k++,j--)
        {
            swap=buffer[k];
            buffer[k]=buffer[j];
            buffer[j]=swap;
        }
        strcpy(dict[dictlength],buffer);
        dictlength++;
    }
    for(i=0;i<dictlength;i++)
        puts(dict[i]);
}

Upvotes: 2

tobias_k
tobias_k

Reputation: 82899

Here's another version, using recursion. This one uses just integer division and modulo (both combined in divmod) to get the 'sub-integers'. It's done in Python, which is just as good as pseudo code...

def subints(n):
    d, r = divmod(n, 10)
    if d > 0:
        for s in subints(d):
            yield 10*s + r
            yield    s
    yield r

Example: (a set of the resulting numbers would be enough; using list for better understanding)

>>> print list(subints(1234))
[1234, 123, 124, 12, 134, 13, 14, 1, 234, 23, 24, 2, 34, 3, 4]

Upvotes: 2

svinja
svinja

Reputation: 5576

How about this:

    static HashSet<string> Subseq(string input, HashSet<string> result = null, int pos = 0, string current = "")
    {
        if (result == null)
        {
            result = new HashSet<string>();
        }

        if (pos == input.Length)
        {
            return result;
        }

        Subseq(input, result, pos + 1, current);

        current += input[pos];
        if (!result.Contains(current))
        {
            result.Add(current);
        }

        Subseq(input, result, pos + 1, current);

        return result;
    }

Called as:

var result = Subseq("18923928");

If you don't consider "123" a subsequence of "123", then just add the condition current != input to the last if.

Upvotes: 1

Related Questions