Is there a algorithm to print all arrengments of subsequences of an array?

Question

I am working with combinatorics and I would like to know if there is an algorithm that prints all arrangments of subsequences of a given array. That is, if I give to this algorithm the sequence "ABCDEF" it will print :

A, B, C, D, E, F,
AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF, EF,
ABC, ABD, ABE, ABF, ACD, ACE, ACF, ADE, ADF, AEF, BCD, BCE, BCF, BDE, BDF, BEF, CDE, CDF, CEF, DEF,
ABCD, ABCE, ABCF, ABDE, ABDF, ABEF, ACDE, ACDF, ACEF, ADEF, BCDE, BCDF, BCEF, BDEF, CDEF,
ABCDE, ABCDF, ABCEF, ABDEF, ACDEF, BCDEF, ABCDEF,

or for a more simple case, if i give it 1234, it will print:

1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234.

As you can see it is not an arbitrary permutation it is only the permutation of the last members of a subsequence in a way it still reains a subsequence.

I have tried to make a function in c that does this but i got really confused, my idea would be to make a int L that keeps the size of the subsequence,and another tree integers one that keeps the head of the subsequence, one that marks the separation from the head and one that slides trought the given number of characters, but it gets too confused too quickly.

Can anyone help me with this ?

my code is:

int Stringsize( char m[] ){

     int k;
     for(k=0;;k++){
     if( m[k] == '\0') break;    
     }
return (k-1);

}


void StringOrdM(char m[]){
    int q,r,s,k; 
    for(k=0;k<=Stringsize(m);k++)
       for(q=0;q<=Stringsize(m);q++)
          for(s=q;s<=Stringsize(m);s++ )
              printf("%c",m[q]);
          for(r=q+1; r<=Stringsize(m) && (r-q+1)<= k ;r++ )
              printf("%c", m[r] );

}

And for ABCD it prints A,A,A,A,B,B,B,C,C,D,AA,AB,AC,AD,BC,BD,CC,CD,DD,... so it is not right because it keeps repeating the A 4 times the B three times and so on, when it should have been A,B,C,D,AB,AC,AD,BC,BD,CD,...

Answer 1

As I said in my comment above, one solution is simple: count in binary up to (1<<n)-1.

So if you have four items, count up to 15, with each bit pattern being a selection of the elements. You'll get 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. Each bit is a true/false value as to whether to include that element of the array.

#include <stdio.h>

int main(void) {
  ////////////////////////////////////////////////////////////////////////
  int A[] = { 1, 2, 3, 4, 5 };
  ////////////////////////////////////////////////////////////////////////

  size_t len = sizeof A / sizeof A[0];    // Array length (in elements)
  size_t elbp = (1<<len) - 1;             // Element selection bit pattern
  size_t i, j;                            // Iterators

  // Cycle through all the bit patterns
  for (i = 1; i<=elbp; i++) {
    // For each bit pattern, print out the 'checked' elements
    for (j = 0; j < len; j++) {
      if (i & (1<<j)) printf("%d ", A[j]);
    }
    printf("\n");
  }

  return 0;
}

If you want the elements sorted shortest to longest, you could always store these results in a string array (using sprintf()) and then sort (using a stable sorting algorithm!) by string length.

Answer 2

I mentioned in a comment above that if you didn't want to use a bit pattern to find all permutations, and sort the results according to whatever criteria you'd like, you could also use a recursive algorithm.

I suspect this is a homework assignment, and you only asked for an algorithm, so I left some of the key code as an exercise for you to finish. However, the algorithm itself is complete (the key parts are just described in comments, rather than functional code being inserted).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void printpermutations(const int *A, const size_t n, const char *pfix, const size_t rd);


int main(void) {
  /////////////////////////////////////////////////////////////////////
  int A[] = { 1, 2, 3, 4, 5 };
  /////////////////////////////////////////////////////////////////////
  size_t n = sizeof A / sizeof A[0];    // Array length (in elements)
  size_t i;                             // Iterator

  for (i = 1; i <= n; i++) {
    printpermutations(A, n, "", i);
  }

  return 0;
}


// Recursive function to print permutations of a given length rd,
// using a prefix set in pfix.
// Arguments:
//   int *A       The integer array we're finding permutations in
//   size_t n     The size of the integer array
//   char *pfix   Computed output in higher levels of recursion,
//                which will be prepended when we plunge to our
//                intended recursive depth
//   size_t rd    Remaining depth to plunge in recursion
void printpermutations(const int *A, const size_t n, const char *pfix, const size_t rd) {
  size_t i;
  char newpfix[strlen(pfix)+22];  // 20 digits in 64-bit unsigned int
                                  // plus a space, plus '\0'

  if (n < rd) return;             // Don't bother if we don't have enough
                                  // elements to do a permutation

  if (rd == 1) {
    for (i = 0; i < n; i++) {
      // YOUR CODE HERE
      // Use printf() to print out:
      //   A string, consisting of the prefix we were passed
      //   Followed immediately by A[i] and a newline
    }
  }

  else {
    strcpy(newpfix, pfix);
    for (i = 1; i <= n; i++) {
      // YOUR CODE HERE
      // Use sprintf() to put A[i-1] and a space into the new prefix string
      //   at an offset of strlen(pfix). 
      // Then, call printpermutations() starting with the ith offset into A[],
      //   with a size of n-i, using the new prefix, with a remaining
      //   recursion depth one less than the one we were called with
    }
  }
}

Answer 3

Depending on torstenvl's answer I did this code and It works perfectly.

If there is any problem let me know.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) 
{
   char str[] = "1234"; 
   size_t len = strlen(str);                 // Array length (in elements)
   char *A = malloc(sizeof(char) * len);
   strcpy(A,str);

   size_t elbp = (1<<len) - 1;             // Element selection bit pattern
   size_t i, j;                            // Iterators
   int a = 0, b = 0, n = 0;
   char **arr = malloc(sizeof(char*) * (10000));      //allocating memory

if (A[0] >= 'A' && A[0] <= 'Z')          //If the string given is "ABCD...." transfer 'A' to '1' ; 'C' to '3' ...etc
    for(int i = 0; i < len; i++)
        A[i] = A[i] - 'A' + '1';

// Cycle through all the bit patterns
for (i = 1; i<=elbp; i++)
{
    arr[b] = malloc(sizeof(char) * len);

    // For each bit pattern, store in arr[b] the 'checked' elements
    for (j = 0, a = 0; j < len; j++) 
        if (i & (1<<j))
            arr[b][a++] = A[j]; 
    b++;
}

int *num = calloc(sizeof(int) ,10000);

for (i = 0; i < b; i++) 
    num[i] = strtol(arr[i], NULL, 10);     //convert char to int

for (i = 0; i < b; i++)                   //sort array numbers from smallest to largest
    for (a = 0; a < i; a++)
        if (num[i] < num[a])
        {
            n = num[i];
            num[i] = num[a];
            num[a] = n;
        }

char *result = calloc(sizeof(char),10000);

for (i = 0, a = 0; i<b; i++)
    a += sprintf(&result[a], "%d,", num[i]);     //convert int to char and store it in result[a]

result[a - 1] = '\0';    //remove the last ','
len = strlen(result);

if (str[0] >= 'A' && str[0] <= 'Z')              //if the string given is "ABCD..." transfer '1' to 'A' ; '12' to 'AB' ; '13' to 'AC'.....etc
    for (i = 0; i < len; i++)
        if(result[i] != ',')
            result[i] = 'A' + (result[i] - '1') ;

  ///test
  printf("%s",result);

  return 0;
}

the output for "1234":

1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234

the output for "123456789":

1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49,56,57,58,59,67,68,69,78,79,89,123,124,125,126,127,128,129,134,135,136,137,138,139,145,146,147,148,149,156,157,158,159,167,168,169,178,179,189,234,235,236,237,238,239,245,246,247,248,249,256,257,258,259,267,268,269,278,279,289,345,346,347,348,349,356,357,358,359,367,368,369,378,379,389,456,457,458,459,467,468,469,478,479,489,567,568,569,578,579,589,678,679,689,789,1234,1235,1236,1237,1238,1239,1245,1246,1247,1248,1249,1256,1257,1258,1259,1267,1268,1269,1278,1279,1289,1345,1346,1347,1348,1349,1356,1357,1358,1359,1367,1368,1369,1378,1379,1389,1456,1457,1458,1459,1467,1468,1469,1478,1479,1489,1567,1568,1569,1578,1579,1589,1678,1679,1689,1789,2345,2346,2347,2348,2349,2356,2357,2358,2359,2367,2368,2369,2378,2379,2389,2456,2457,2458,2459,2467,2468,2469,2478,2479,2489,2567,2568,2569,2578,2579,2589,2678,2679,2689,2789,3456,3457,3458,3459,3467,3468,3469,3478,3479,3489,3567,3568,3569,3578,3579,3589,3678,3679,3689,3789,4567,4568,4569,4578,4579,4589,4678,4679,4689,4789,5678,5679,5689,5789,6789,12345,12346,12347,12348,12349,12356,12357,12358,12359,12367,12368,12369,12378,12379,12389,12456,12457,12458,12459,12467,12468,12469,12478,12479,12489,12567,12568,12569,12578,12579,12589,12678,12679,12689,12789,13456,13457,13458,13459,13467,13468,13469,13478,13479,13489,13567,13568,13569,13578,13579,13589,13678,13679,13689,13789,14567,14568,14569,14578,14579,14589,14678,14679,14689,14789,15678,15679,15689,15789,16789,23456,23457,23458,23459,23467,23468,23469,23478,23479,23489,23567,23568,23569,23578,23579,23589,23678,23679,23689,23789,24567,24568,24569,24578,24579,24589,24678,24679,24689,24789,25678,25679,25689,25789,26789,34567,34568,34569,34578,34579,34589,34678,34679,34689,34789,35678,35679,35689,35789,36789,45678,45679,45689,45789,46789,56789,123456,123457,123458,123459,123467,123468,123469,123478,123479,123489,123567,123568,123569,123578,123579,123589,123678,123679,123689,123789,124567,124568,124569,124578,124579,124589,124678,124679,124689,124789,125678,125679,125689,125789,126789,134567,134568,134569,134578,134579,134589,134678,134679,134689,134789,135678,135679,135689,135789,136789,145678,145679,145689,145789,146789,156789,234567,234568,234569,234578,234579,234589,234678,234679,234689,234789,235678,235679,235689,235789,236789,245678,245679,245689,245789,246789,256789,345678,345679,345689,345789,346789,356789,456789,1234567,1234568,1234569,1234578,1234579,1234589,1234678,1234679,1234689,1234789,1235678,1235679,1235689,1235789,1236789,1245678,1245679,1245689,1245789,1246789,1256789,1345678,1345679,1345689,1345789,1346789,1356789,1456789,2345678,2345679,2345689,2345789,2346789,2356789,2456789,3456789,12345678,12345679,12345689,12345789,12346789,12356789,12456789,13456789,23456789,123456789

the output for "ABCDEF":

A,B,C,D,E,F,AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF,ABC,ABD,ABE,ABF,ACD,ACE,ACF,ADE,ADF,AEF,BCD,BCE,BCF,BDE,BDF,BEF,CDE,CDF,CEF,DEF,ABCD,ABCE,ABCF,ABDE,ABDF,ABEF,ACDE,ACDF,ACEF,ADEF,BCDE,BCDF,BCEF,BDEF,CDEF,ABCDE,ABCDF,ABCEF,ABDEF,ACDEF,BCDEF,ABCDEF

Answer 4

Combinations, or k-combinations, are the unordered sets of k elements chosen from a set of size n. Source: http://www.martinbroadhurst.com/combinations.html This is the code:

unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    if (k > 0) {
        for (i = k - 1; !finished && !changed; i--) {
            if (ar[i] < (n - 1) - (k - 1) + i) {
                /* Increment this element */
                ar[i]++;
                if (i < k - 1) {
                    /* Turn the elements after it into a linear sequence */
                    unsigned int j;
                    for (j = i + 1; j < k; j++) {
                        ar[j] = ar[j - 1] + 1;
                    }
                }
                changed = 1;
            }
            finished = i == 0;
        }
        if (!changed) {
            /* Reset to first combination */
            for (i = 0; i < k; i++) {
                ar[i] = i;
            }
        }
    }
    return changed;
}