求不重复数据的全排列

ゝ一世哀愁。 2022-09-29 06:02 172阅读 0赞

学计算机这么久了还不会这个，有点说不过去。今天看了看。算法还是比较容易理解的。

比如，可以使用递归将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为

1 \[2 3 4\] 、2 \[1 3 4\]、3 \[1 2 4\]、4 \[1 2 3\]进行排列，

这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：

1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递归处理

2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递归处理

3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递归处理

4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递归处理

代码如下：

public class test {
    	public static void main(String args[]) {
    		int[] cs = new int[5];
    		for (int j = 0; j < cs.length; j++) {
    			cs[j] = j + 1;
    		}
    		getPerm(cs, 0);
    	}
    	public static void getPerm(int[] cs, int i) {
    		if (i < cs.length - 1) {
    			for (int j = i; j < cs.length; j++) {
    				int temp = cs[j];
    				// 右移数据
    				for (int k = j; k > i; k--)
    					cs[k] = cs[k - 1];
    				cs[i] = temp;
    				getPerm(cs, i + 1);
    				//每次都要把数据恢复之后才可以进行下一次排列
    				for (int k = i; k < j; k++)
    					cs[k] = cs[k + 1];
    				cs[j] = temp;
    			}
    		} else {// 如果i是cs.length()-1的话，那么说明已经排列到最后一个元素，可以不用继续排列了，输出该数组既可以
    			for (int m = 0; m < cs.length; m++)
    				System.out.print(cs[m]);
    			System.out.println();
    		}
    	}
    }

如果要求按照大小输出的话，只需要在排序之前，对需要排序的数字进行排序。

\--------------------------------------------------------魂歌----------------------------------------------------------

正式开始找工作了。不论找实习还是工作，都要复习一下算法。这次自己写了一下这个算法，还算写的不错吧，思路比较清晰。看来算法就是越用越熟练了。

package zoer;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class CopyOfT {
    	static int count = 0;
    
    	public static void main(String args[]) {
    		get("1234", new ArrayList<String>());
    		System.out.println("全排列个数为："+count);
    	}
    
    	public static void get(String s, List<String> list) {
    		if (s.length() == 1) {
    			count++;
    			for (int i = 0; i < list.size(); i++) {
    				System.out.print(list.get(i));
    			}
    			System.out.println(s);
    		} else {
    			for (int i = 0; i < s.length(); i++) {
    				list.add("" + s.charAt(0));
    				String sub = s.substring(1, s.length());
    				get(sub, list);
    				s = sub + s.charAt(0);
    				list.remove(list.size() - 1);
    			}
    		}
    	}
    }

每次把下一个字符提到字符串的最前端，对剩余的字串做相同的操作。直到剩余的子字符串的长度为1的时候，输出得到的全排列结果。

上面的代码中，s = sub + s.charAt(0);的意思是说，第一个字符处理完毕之后，把它加到字符串的末尾，然后处理第二个字符。依次类推直到所有的字符都处理完毕【这里说的处理，具体就是指把一个字符摘出来，对其他剩余的字符串做全排列】。

\------------------------------------------------------------------------------

上面的算法是对一个非重复字符串的全排列，但是没有按照原来的字符中字符顺序来输出，主要是因为在移动字符的时候，直接s = sub + s.charAt(0);这样的结果是第一个字符直接跑到最后去了。而不是跟相应的字符进行交换，那么按照下面的代码，即可实现按照”字符原来“的顺序进行输出。

package zoer;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class CopyOfT {
    	static int count = 0;
    
    	public static void main(String args[]) {
    		get("1234", new ArrayList<String>());
    		System.out.println("全排列个数为：" + count);
    	}
    
    	public static void get(String s, List<String> list) {
    		if (s.length() == 1) {
    			count++;
    			for (int i = 0; i < list.size(); i++) {
    				System.out.print(list.get(i));
    			}
    			System.out.println(s);
    		} else {
    			for (int i = 0; i < s.length(); i++) {
    				list.add("" + s.charAt(0));
    				String sub = s.substring(1, s.length());
    				get(sub, list);
    				if (i != s.length() - 1) {
    					s = s.charAt(i + 1) + s.substring(0, i + 1)
    							+ s.substring(i + 2, s.length());
    				}
    				list.remove(list.size() - 1);
    			}
    		}
    	}
    }

不过上面的这个算法是求不重复字串的全排列。重复的还要再考虑下,,,

\---------------------------------------------有重复的情况--------------------------------------------

这里考虑了有重复的情况。如果重复的字符在字符串中不是第一次出现，那么就不用递归这个字符了。用一个数组来记录每一个字符在字符串中第一次出现的位置。

实现代码如下：

package zoer;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class CopyOfT {
    	static int count = 0;
    
    	public static void main(String args[]) {
    		String s = "1223";
    		get(s, new ArrayList<String>());
    		System.out.println("全排列个数为：" + count);
    	}
    
    	public static void get(String s, List<String> list) {
    		if (s.length() == 1) {
    			count++;
    			for (int i = 0; i < list.size(); i++) {
    				System.out.print(list.get(i));
    			}
    			System.out.println(s);
    		} else {
    			int index[] = new int[s.length()];
    			for (int i = 0; i < index.length; i++) {
    				index[i] = s.indexOf(s.charAt(i));// 用index数组记录字符串中相应位置的字符在字符串中第一次出现的位置
    			}
    			for (int i = 0; i < s.length(); i++) {
    				String sub = s.substring(1, s.length());
    				// 如果一个数不在他第一次出现的位置，那么这个字符是重复的，跳过这个字符；否则才递归
    				if (i == index[i]) {// 查看第i个字符在字符串中出现的位置是不是与i相同，如果不同，说明是重复的
    					list.add("" + s.charAt(0));
    					get(sub, list);
    					list.remove(list.size() - 1);
    				}
    				s = sub + s.charAt(0);
    			}
    		}
    	}
    }