字符数组的每种组合 [英] Every combination of character array

问题描述

尝试显示数组字符的每个组合而不重复字母时出现问题.

Having problems trying to show every combination of a character of array without repeating letters.

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else
    {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        //append the sublists to each element
        int arrayIndex = 0;

        for(int i = 0; i < elements.length; i++)
        {
            for(int j = 0; j < allSublists.length; j++)
            {
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }

        return allLists;
    }
}

上面的代码可以完美地工作，但是每个字母不能重复使用一次，在这种情况下是不能做到的.

The above code works perfect but use's each letter more than once which cant be done in this case.

现在我被困在该怎么做.

And i am stuck how to do this now.

推荐答案

这是一个示例实现.本质上，它需要一个String并遍历每个字符，然后将该字符放在最前面.然后，它在其余字符上递归.这种结构消除了重复字母的问题，因为递归的输入已删除了您已经使用过的字符.

Here's an example implementation. Essentially it takes a String and iterates over every character, putting that character at the front. It then recurses on the remaining characters. That structure removes your issue of repeated letters, because the input to the recursion has removed the character you've already used.

我还将结果存储在一个集合中，以消除语义上的对等.输入"aab"可以切换char 0和char 1，但仍为"aab".我使用TreeSet保留顺序以便更轻松地验证输出，但是HashSet会更快.

I also stored results in a set to remove semantic equivalences. The input 'aab' can switch char 0 and char 1 but still be 'aab.' I used a TreeSet to preserve ordering for easier verification of the output, but HashSet would be faster.

  public static Set<String> permute(String chars)
  {
    // Use sets to eliminate semantic duplicates (aab is still aab even if you switch the two 'a's)
    // Switch to HashSet for better performance
    Set<String> set = new TreeSet<String>();

    // Termination condition: only 1 permutation for a string of length 1
    if (chars.length() == 1)
    {
      set.add(chars);
    }
    else
    {
      // Give each character a chance to be the first in the permuted string
      for (int i=0; i<chars.length(); i++)
      {
        // Remove the character at index i from the string
        String pre = chars.substring(0, i);
        String post = chars.substring(i+1);
        String remaining = pre+post;

        // Recurse to find all the permutations of the remaining chars
        for (String permutation : permute(remaining))
        {
          // Concatenate the first character with the permutations of the remaining chars
          set.add(chars.charAt(i) + permutation);
        }
      }
    }
    return set;
  }

示例运行:

  public static void main(String[] args)
  {
    for (String s : CharPermuter.permute("abca"))
    {
      System.out.println(s);
    }
  }

生成:

aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

这篇关于字符数组的每种组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！