16 Permutation and Combination in JavaScript

p&c.js

/*

Permutation in mathmatics stands for all possible order for a set.
Combination in mathmatics stands for all possible ways of selecting items from a set.
Find more at 
https://en.wikipedia.org/wiki/Permutation
https://en.wikipedia.org/wiki/Combination

*/

function permutations(arr){
  // base case where array only contains one element
  if(arr.length == 1){
    return [arr];
  }else{
  // recursive case where the array is divided into its head and tail
    var result = [];
    for (var i = 0; i < arr.length; i++) {
      // remember to use the copy of array for each loop
      var _arr = arr.slice();
      var head = _arr.splice(i, 1);
      // recursively call permutations() on the tail of array
      var tail = permutations(_arr);
      // for each permutations of the tail, concat it to the head as a result
      for (var j = 0; j < tail.length; j++) {
        result.push(head.concat(tail[j]));
      }
    }
    return result;
  }
}

// test
var result = permutations([0,1,2,3]);
console.log(result);

/* result

[ [ 0, 1, 2, 3 ],
  [ 0, 1, 3, 2 ],
  [ 0, 2, 1, 3 ],
  [ 0, 2, 3, 1 ],
  [ 0, 3, 1, 2 ],
  [ 0, 3, 2, 1 ],
  [ 1, 0, 2, 3 ],
  [ 1, 0, 3, 2 ],
  [ 1, 2, 0, 3 ],
  [ 1, 2, 3, 0 ],
  [ 1, 3, 0, 2 ],
  [ 1, 3, 2, 0 ],
  [ 2, 0, 1, 3 ],
  [ 2, 0, 3, 1 ],
  [ 2, 1, 0, 3 ],
  [ 2, 1, 3, 0 ],
  [ 2, 3, 0, 1 ],
  [ 2, 3, 1, 0 ],
  [ 3, 0, 1, 2 ],
  [ 3, 0, 2, 1 ],
  [ 3, 1, 0, 2 ],
  [ 3, 1, 2, 0 ],
  [ 3, 2, 0, 1 ],
  [ 3, 2, 1, 0 ] ]

*/

function combinations(arr){
  // base case where array contains no element
  if(arr.length == 0){
    return [[]];
  }else{
  // recursive case where the array is divided into the last element and the rest elements
    var last = arr.pop();
    // get the combinations for all elements
    var result = combinations(arr);
    // get the length of result before loop to avoid infinite loop
    var length = result.length
    // append the last element to the tail to generate a bunch of new combinations 
    for (var i = 0; i < length; i++) {
      // copy the array element
      var c = result[i].slice();
      c.push(last);
      result.push(c);
    }
    return result;
  }
}

// test
var result = combinations([0,1,2,3]);
console.log(result);

/* result

[ [],
  [ 0 ],
  [ 1 ],
  [ 0, 1 ],
  [ 2 ],
  [ 0, 2 ],
  [ 1, 2 ],
  [ 0, 1, 2 ],
  [ 3 ],
  [ 0, 3 ],
  [ 1, 3 ],
  [ 0, 1, 3 ],
  [ 2, 3 ],
  [ 0, 2, 3 ],
  [ 1, 2, 3 ],
  [ 0, 1, 2, 3 ] ]
  
*/

permutation.c

// an implementation in c of the above permutation algorithm

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

// string concatenation
char* my_strcat(char* str1, char* str2) {
  int sumlen = (int)strlen(str1) + (int)strlen(str2) + 1;
  char* result = (char*)malloc(sizeof(char) * sumlen);
  int i = 0;
  while(str1[i] != '\0') {
    result[i] = str1[i];
    i++;
  }
  int j = 0;
  while(str2[j] != '\0') {
    result[i + j] = str2[j];
    j++;
  }
  return result;
}

// concat a char head to a string tail
char* ctos(char head, char* tail) {
  char* _head = (char*)malloc(sizeof(char));
  _head[0] = head;
  return my_strcat(_head, tail);
}

// remove one char from string and return, the remainder will be stored in spliced
char splice(char* str, int index, char* spliced) {
  char result = '\0';
  for (int i = 0; i < strlen(str); i++) {
    if (i < index) {
      spliced[i] = str[i];
    } else {
      spliced[i] = str[i + 1];
    }
    if (i == index) {
      result = str[i];
    }
  }
  return result;
}

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

char** permute(char* str) {
  int len = (int)strlen(str);
  if (len == 1) {
    char* _str = (char*)malloc(sizeof(char) * 2);
    _str[0] = str[0];
    char** result = (char**)malloc(sizeof(char*));
    result[0] = _str;
    return result;
  } else {
    int inc = 0;
    char** result = (char**)malloc(sizeof(char*) * factorial(len));
    for (int i = 0; i < len; i++) {
      char* tail = (char*)malloc(sizeof(char) * len);
      char head = splice(str, i, tail);
      char** permutations = permute(tail);
      for (int j = 0; j < factorial(len - 1); j++) {
        char* permutation = permutations[j];
        char* aresult = ctos(head, permutation);
        result[inc++] = aresult;
      }
    }
    return result;
  }
}

int main() {
  char str[] = "0123";
  char** permutations = permute(str);
  for (int i = 0; i < factorial((int)strlen(str)); i++) {
    printf("%s\n", permutations[i]);
  }
  free(permutations);
}

/*
 0123
 0132
 0213
 0231
 0312
 0321
 1023
 1032
 1203
 1230
 1302
 1320
 2013
 2031
 2103
 2130
 2301
 2310
 3012
 3021
 3102
 3120
 3201
 3210
*/