找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?


当前回答

让我试着用Kotlin来解决这个问题:

fun <T> List<T>.permutations(): List<List<T>> {
    //escape case
    if (this.isEmpty()) return emptyList()

    if (this.size == 1) return listOf(this)

    if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))

    //recursive case
    return this.flatMap { lastItem ->
        this.minus(lastItem).permutations().map { it.plus(lastItem) }
    }
}

核心概念:将长链表分解成小链表+递归

长答案与示例列表[1,2,3,4]:

即使是一个4种组合的列表,在脑海中列出所有可能的排列已经有点令人困惑了,我们需要做的就是避免这种情况。我们很容易理解如何对大小为0、1和2的列表进行排列,因此我们所需要做的就是将它们分解为这些大小中的任何一个,并将它们正确地组合起来。想象一台头奖机器:这个算法将从右向左旋转,然后写下

当列表大小为0或1时,返回空/列表为1 当列表大小为2时处理(例如[3,4]),并生成2个排列([3,4]& [4,3]) 对于每一项,将其标记为最后一项中的最后一项,并找到列表中其余项目的所有排列。(例如,把[4]放在桌子上,把[1,2,3]重新排列) 现在对它的子元素进行所有的排列,把它自己放回列表的末尾(例如:[1,2,3][,4],[1,3,2][,4],[2,3,1][,4],…)

其他回答

//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合

public class Permutation {
    //Act as a queue
    private List<Character> list;
    //To remove the duplicates
    private Set<String> set = new HashSet<String>();

    public Permutation(String s) {
        list = new LinkedList<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            list.add(s.charAt(i));
        }
    }

    public List<String> getStack(Character c, List<Character> list) {
        LinkedList<String> stack = new LinkedList<String>();
        stack.add(""+c);
        for(Character ch: list) {
            stack.add(""+ch);
        }

        return stack;
    }

    public String printCombination(String s1, String s2) {
        //S1 will be a single character
        StringBuilder sb = new StringBuilder();
        String[] strArr = s2.split(",");
        for(String s: strArr) {
            sb.append(s).append(s1);
            sb.append(",");
        }       
        for(String s: strArr) {
            sb.append(s1).append(s);
            sb.append(",");
        }

        return sb.toString();
    }

    public void printPerumtation() {
        int cnt = list.size();

        for(int i = 0; i < cnt; i++) {
            Character c = list.get(0);
            list.remove(0);
            List<String> stack = getStack(c, list);

            while(stack.size() > 1) {
                //Remove the top two elements
                String s2 = stack.remove(stack.size() - 1);
                String s1 = stack.remove(stack.size() - 1);
                String comS = printCombination(s1, s2);
                stack.add(comS);
            }

            String[] perms = (stack.remove(0)).split(",");
            for(String perm: perms) {
                set.add(perm);
            }

            list.add(c);
        }

        for(String s: set) {
            System.out.println(s);
        }
    }
}
/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

在这里和其他论坛给出的所有解决方案中,我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案,因为我是新手。 无论如何,这是我对他的描述的实现

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}   

我更喜欢这个解决方案,而不是第一个解决方案,因为这个解决方案使用StringBuffer。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建,其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说,由于额外的“交换”,它已经滞后了)

下面是一个简单的Java递归解决方案:

public static ArrayList<String> permutations(String s) {
    ArrayList<String> out = new ArrayList<String>();
    if (s.length() == 1) {
        out.add(s);
        return out;
    }
    char first = s.charAt(0);
    String rest = s.substring(1);
    for (String permutation : permutations(rest)) {
        out.addAll(insertAtAllPositions(first, permutation));
    }
    return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
    ArrayList<String> out = new ArrayList<String>();
    for (int i = 0; i <= s.length(); ++i) {
        String inserted = s.substring(0, i) + ch + s.substring(i);
        out.add(inserted);
    }
    return out;
}

使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }