含有重复字符的字符数组的全排列

笔试中遇到了3次这道题，题目大致是这样的：请编写代码实现有重复元素的全排列问题  。

整理了下思路，写了个java代码， 这个代码既可以针对有重复元素的全排列，又可以针对无重复元素的全排列

public class repeatAllArray {
 /*
  * allArray实现含有重复字符的数组的全排列
  * list是含重复字符的数组，i是指示当前位置的游标，length是数组长度
  * 注释：这个函数最核心的地方，我感觉是else块的代码
  */
 public void allArray(char list[], int i, int length) {
  if (i == length - 1) {
   for (int j = 0; j < length; j++) {
    System.out.print(list[j]);
   }
   System.out.println();
  } else {
   for (int j = i; j < length; j++) {
    if (!isExist(list, i, j)) {
     swap(list, i, j);// 交换当前值和当前位置之后的值
     allArray(list, i + 1, length);// 当前位置+1，递归
     swap(list, i, j);// 再交换
    }
   }
  }
 }
 
    /*
     * isExist判断j位置的字符是否已经在list[0]~list[j-1]中出现过了
     * list是含重复字符的数组，i是指示当前位置的游标，j是要判断的字符的位置
     */
 public boolean isExist(char list[], int i, int j) {
  for (int k = i; k < j; k++) {
   if (list[j] == list[k]) {
    return true;
   }
  }
  return false;
 }

 /*
  * swap实现了数组中两个位置的值的交换
  * list是含重复字符的数组，i,j表示要交换的位置
  */
 public void swap(char list[], int i, int j) {
  char temp = list[i];
  list[i] = list[j];
  list[j] = temp;
 }

 public static void main(String[] args) {
  char a[] = { 'a', 'a', 'b', 'b' };//以这个字符数组为例
  repeatAllArray array = new repeatAllArray();
  array.allArray(a, 0, a.length);
 }

}

评论

4 楼 功夫小当家 2012-10-18  

那个，建议一下楼主下次发代码要用插入代码，不要直接粘贴，直接粘贴的代码不能收藏啊

好的，谢谢你的建议~

3 楼 Chris_bing 2012-10-17  

那个，建议一下楼主下次发代码要用插入代码，不要直接粘贴，直接粘贴的代码不能收藏啊

应该这样：

public class repeatAllArray {
 /*
  * allArray实现含有重复字符的数组的全排列
  * list是含重复字符的数组，i是指示当前位置的游标，length是数组长度
  * 注释：这个函数最核心的地方，我感觉是else块的代码
  */
 public void allArray(char list[], int i, int length) {
  if (i == length - 1) {
   for (int j = 0; j < length; j++) {
    System.out.print(list[j]);
   }
   System.out.println();
  } else {
   for (int j = i; j < length; j++) {
    if (!isExist(list, i, j)) {
     swap(list, i, j);// 交换当前值和当前位置之后的值
     allArray(list, i + 1, length);// 当前位置+1，递归
     swap(list, i, j);// 再交换
    }
   }
  }
 }
 
    /*
     * isExist判断j位置的字符是否已经在list[0]~list[j-1]中出现过了
     * list是含重复字符的数组，i是指示当前位置的游标，j是要判断的字符的位置
     */
 public boolean isExist(char list[], int i, int j) {
  for (int k = i; k < j; k++) {
   if (list[j] == list[k]) {
    return true;
   }
  }
  return false;
 }
 /*
  * swap实现了数组中两个位置的值的交换
  * list是含重复字符的数组，i,j表示要交换的位置
  */
 public void swap(char list[], int i, int j) {
  char temp = list[i];
  list[i] = list[j];
  list[j] = temp;
 }
 public static void main(String[] args) {
  char a[] = { 'a', 'a', 'b', 'b' };//以这个字符数组为例
  repeatAllArray array = new repeatAllArray();
  array.allArray(a, 0, a.length);
 }
}

2 楼 功夫小当家 2012-10-17  

Chris_bing 写道

带重复的全排列居然就比不带重复的全排列多了一个判断条件...我之前想了好久啊!

恩，得去重，要不然会多算

1 楼 Chris_bing 2012-10-17  

带重复的全排列居然就比不带重复的全排列多了一个判断条件...我之前想了好久啊!