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

これを定義するより良い方法は、2 つの別個の操作として考えることです。

最初に、入力文字列のすべてのサブセットを生成しています (これは と呼ばれますpower set)

次に、これらのサブセットの 1 つを指定して、指定された長さで順列のリストを生成しています。

最初の操作を実行する関数を作成し、各出力セットを入力として 2 番目の操作に渡すと、理論的には結果が生成されます。

コードでは、次のように考えてください。

// 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();
}

ご覧のとおり、このアプローチは理論的には正しいものの、パワーセットを再帰的に生成するために大量のヒープ スペースとスタック スペースを使用するため、最適なアプローチではない可能性があります。一方、順列の生成はそれほど難しくありません。

Answer 3

このようなことを試してください:-

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 );   
    }
 }