Java實現從m個各不相同的元素中取出n個，并進行全排列。

2019-11-06 09:33:30

字體：大中小

來源：轉載

供稿：網友

　　最近在看面試題的時候發現，一些基礎的算法都記不住了，只是能大概說出個原理….為了加深記憶，這里對一些簡單的算法題進行一個歸納。

　　下面的代碼主要解決的問題是：從m個各不相同的元素中取出n個，進行全排列，得到所有可能的結果。　　即：輸入為字符數組（數組內每個字符均不相同）和個數n，返回由這些字符組成的所有長度為n的字符串。

測試用例樣例：　　輸入為{‘a’,’b’,’c’}和個數1，返回值為{“a”,”b”,”c”} 　　輸入為{‘a’,’b’,’c’,’d’}和個數2，返回值為{“ab”,”ac”,”ad”,”ba”,”bc”,”bd”,”ca”,”cb”,”cd”,”da”,”db”,”dc”}

下面是java實現：

import java.util.ArrayList;import java.util.List;/** * Created by Flynnon on 17-2-26. */public class ListChars { /** * @param chars 總的字符序列（數組） * @param n 要取出的字符的個數 */ public static void doit(char[] chars, int n) { if (n <= 0 || chars == null) { return; } List<Character> charList = new ArrayList<>(); //通過這一步初始化序列的長度 for (int i = 0; i < n; i++) { charList.add('#'); } listAll(charList, chars, n); } /** * 從m個元素中任取n個并對結果進行全排列 * @param list 用于承載可能的排列情況的List * @param chars 總的字符數組，長度為m * @param n 從中取得字符個數 */ public static void listAll(List<Character> list, char[] chars, int n) { if (n == 0) { //這里偷懶，直接打印了.... System.out.PRintln(list); // 輸出一種可能的排列 return; } for (char aChar : chars) { // 暴力嘗試 if (!list.contains(aChar)) { // 若List中不包含這一位元素 list.set(list.size() - n, aChar); // 將當前元素加入 } else { // 否則跳到下一位 continue; } listAll(list, chars, n - 1); // 下一位 list.set(list.size() - n, '#'); // 還原 } } public static void main(String[] args) { // 以字符數組承載總的字符集合 char[] chars = {'a', 'b', 'c', 'd'}; ListChars.doit(chars, 2); }}

　　下面是測試用例及結果，與預期結果一致。測試用例一