NCR function

Write a program in C which will print all the possible combination of a given word. E.G. if the word is ABCD then the output should be ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA,
but the number of letters of the input must not be fixed i.e. the program should run well for any number of letters.

megh_dut2008
Profile Answers by megh_dut2008 Questions by megh_dut2008
Jan 9th, 2008
2
2792

Questions by megh_dut2008

Answer

Showing Answers 1 - 2 of 2 Answers

michiw
Profile Answers by michiw

Feb 9th, 2008

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

void ncr(int preflen, char *prefix, int len, char *str) {
if (len <= 1) {
    printf("%s%s, ", prefix, str);
    return;
}

int i;

for (i = 0; i < len; i++) {
    prefix[preflen] = str[i];

    char tmp = str[i];
    str[i] = str[0];
    str[0] = tmp;

    ncr(preflen + 1, prefix, len - 1, str + 1);

    tmp = str[i];
    str[i] = str[0];
    str[0] = tmp;
}
prefix[preflen] = 0;
}

int main(int argc, char** args) {
char *str = args[1];
int len = strlen(str);
char *prefix = calloc(1, len + 1);
ncr(0, prefix, len, str);
}

calvinss4
Profile Answers by calvinss4

Feb 28th, 2008

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

typedef unsigned int u32;

#define SWAP(a, b) do { a ^= b; b ^= a; a ^= b; } while (0)

u32 print_ctr;

void PrintAllPerms(char *str);
void RecurseAllPerms(char *str, u32 len, char *base);

int main()
{
   char buf[50] = "ABCD";
   PrintAllPerms(buf);

   return 0;
}

// Assumes a string of length 2 or greater.
void PrintAllPerms(char *str)
{
   assert(str);
   print_ctr = 0;
   RecurseAllPerms(str, strlen(str), str);
   printf("Perms printed: %un", print_ctr);
}

void RecurseAllPerms(char *str, u32 len, char *base)
{
   if (len == 2)
   {
      printf("%sn", base);
      SWAP(*str, str[1]);
      printf("%sn", base);
      SWAP(*str, str[1]);
      print_ctr += 2;
      return;
   }

   u32 swap_idx = 1;
   RecurseAllPerms(str + 1, len - 1, base);
   while (swap_idx < len)
   {
      SWAP(*str, str[swap_idx]);
      RecurseAllPerms(str + 1, len - 1, base);
      SWAP(*str, str[swap_idx]);
      ++swap_idx;
   }
}