程序员面试攻略　6.2 面试例题：字符串的全排列

/************************************************************************
6.2 面试例题　字符串的全排列
************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/************************************************************************
程序一：
************************************************************************/
void doPermute(char input[], char output[], int used[], int length, int recursLev) {
 int i;

 if (recursLev == length) {
  printf("%s\n", output);
  return;
 }

 for (i = 0; i < length; i++) {
  if (used[i])
   continue;
  output[recursLev] = input[i];
  used[i] = 1;
  doPermute(input, output, used, length, recursLev + 1);
  used[i] = 0;
 }
}

int permute(char instr[]) {
 int length, i, *used;
 char *out;

 length = strlen(instr);
 out = (char*)malloc(length + 1);

 if (out == NULL)
  return 0;
 out[length] = ‘\0‘;

 used = (int*)malloc(sizeof(int)*length);

 if (used == NULL)
  return 0;
 
 for (i = 0; i < length; i++) {
  used[i] = 0;
 }

 doPermute(instr, out, used, length, 0);

 free(out);
 free(used);

 return 1;
}

/************************************************************************
程序二：
************************************************************************/

void swap(char str[], int i, int j) {
 char temp = str[i];
 str[i] = str[j];
 str[j] = temp;
}

 

void doPerm(char str[], int length, int recursLev) {
 int i;
 if (recursLev == length) {
  printf("%s\n", str);
 } else {
  for (i = recursLev; i < length; i++) {
   swap(str, i, recursLev);
   doPerm(str, length, recursLev + 1);
   swap(str, i, recursLev);
  }
  
 }
}

void perm(char str[]) {
 int length;
 length = strlen(str);
 doPerm(str, length, 0);
}

int main() {
 char str[] = "abc";
 permute(str);
 printf("%s\n", "--------------------");
 perm(str);
 return 0;
}