java - 可以由字符组成的字符串组合

Question

如何从Java中的字符数组集中形成不同的字符串组合

例如，

'h' , 'e' , 'l'

结果是，

h
e
l
he
eh
le
el
hl
lh
hel
leh
lhe
hle
ehl    
elh

Answer 1

使用树木。阅读这篇文章：

http://exceptional-code.blogspot.com/2012/09/generating-all-permutations.html

Answer 2

尝试这样的事情： -

void permute( String input)
{
  int inputLength = input.length();
  boolean[ ] used = new boolean[ inputLength ];
  StringBuffer outputString = new StringBuffer();
  char[ ] in = input.toCharArray( );

  doPermute ( in, outputString, used, inputLength, 0 );

}

  void doPermute ( char[ ] in, StringBuffer outputString, 
                    boolean[ ] used, int inputlength, int level)
  {
     if( level == inputLength) {
     System.out.println ( outputString.toString()); 
     return;
     }

    for( int i = 0; i < inputLength; ++i )
    {       

       if( used[i] ) continue;

       outputString.append( in[i] );      
       used[i] = true;       
       doPermute( in,   outputString, used, length, level + 1 );       
       used[i] = false;       
         outputString.setLength(   outputString.length() - 1 );   
    }
 }

Answer 3

定义它的更好方法是将其视为两个独立的操作。

首先，您正在生成输入字符串的所有子集（称为power set）

接下来，您将在给定其中一个子集的情况下生成具有指定长度的排列列表。

创建一个执行第一个操作的函数，然后将每个输出集作为输入传递给第二个操作，理论上会生成结果。

在代码中，请按以下方式考虑：

// Assuming command line params are the input to this operation.
public static void main (String[] args) {
    Set <Set <String>> powerSet = powerSet(new HashSet <String> (Arrays.asList(args)));
    for (Set <String> subset : powerSet) {
        // Permutations need order
        printPermutations(new ArrayList <String> (subset));
    }
}
/*
 * Power set can be generated recursively by considering the two cases: when an element exists in the set, and when the element doesn't exist in the set.
 */ 
public Set <Set <String>> powerSet (Set <String> set) {
   Set <Set <String>> powerSet = new HashSet <Set <String>> ((int)Math.pow(2, set.size()));
   if (set.size() == 0) {
      powerSet.add(new HashSet <String> ());
      return powerSet;
   }
   Set <String> inputCopy = new HashSet <String> (set);
   for (String element : set) {
      inputCopy.remove(element);
      Set <Set <String>> powerSetWithoutElement = powerSet ( inputCopy );
      for (Set <String> subPowerSet : powerSetWithoutElement ) {
          Set <String> powerSetWithElement = new HashSet <String> (subPowerSet);
          powerSetWithElement.add ( element );
          powerSet.add ( powerSetWithElement );
      }
      powerSet.addAll ( powerSetWithoutElement );
   }

   return powerSet;
}

public static void printPermutations(List <String> input) {
   printSubPermutation(input, 0, input.size());
}

public static void printSubPermutation(List <String> input, int startIndex, int endIndex) {
    for (int i = startIndex; i < endIndex; i++) {
        // Swap from start to i
        String temp = input.get(startIndex);
        input.set(startIndex, input.get(i));
        input.set(i, temp);
        // This does: abc -> abc, abc -> bac, abc -> cba
        if (i == endIndex - 1) {
            output(input); // you've reached one permutation here
        } else {
            printSubPermutation(input, startIndex + 1, endIndex);
        }
        // swap back
        String temp = input.get(startIndex);
        input.set(startIndex, input.get(i));
        input.set(i, temp);
    }
}

public static void output(List <String> output) {
    for(String out : output) {
        System.out.print(out + " ");
    }
    System.out.println();
}

如您所见，这种方法虽然理论上正确，但可能不是最好的方法，因为它使用大量的堆空间和堆栈空间来递归地生成 powerset。另一方面，排列的生成并不那么困难。