固定配列順列

Question

私の順列が必要とするものについて誰かが私にいくつかのヒントを与えることができるかどうか疑問に思っていました。

私は文字列「ABC」を持っています。 そして、私は "ABC"の順番を保ちたいが、その周りにはさまざまなバリエーションを入れたい。 たとえば、文字「X」です。相続人は一例

：保存された配列を持つ

考える「ABC」とサイズn = 5、生産List<string>サイズnのそれぞれが、そうn=2の挿入に

A B C X X 
A X B C X 
A X B X C 
A X X B C 
X A B C X 
X A B X C 
X A X B C 
X X A B C 

全体に広がることは非常に簡単です。私はどんなn .....

"ABC"とn=8

A B C X X X X X 

... 

X X A X B X C X 

... 

X X X X X A B C 

にこれを拡張したい だから、このコードは、2-Xの問題のために、 "X" Sのインデックスを与えます... 。

int n = 5; 
for (int i=0; i<n; i++){ 
    for (int j=i+1; j<n; j++) { 
     System.out.println(i + "- " +j); 
    } 
} 

それで一つはiおよびに関連する一つの代わりに、n基づいて出力を生成する場合、任意n与えられたので、これを拡張する方法を...？ 答えは必要ありません。これを拡張する方法のヒントです。私はどれくらいの数のXがあるのか​​、また文字列の長さも知っていません。

ありがとう、 NDG。

Answer 1

すべての組み合わせを生成する1つの方法は、StringBuilderでビルドできる予想サイズのStringがない限り、自分自身を呼び出す再帰的メソッドに頼ることです。再帰性により、あなたの現在の問題であると思われる動的な量のネストされたループを暗黙的に実行することができます。

public static void main(String[] args) { 
    // Permutes to get all possible Strings of size 5 
    System.out.println(permute(5)); 
} 

public static List<String> permute(int n) { 
    List<String> result = new ArrayList<>(); 
    // Initialize the SringBuilder with ABC and the target size 
    permute(n, result, 0, new StringBuilder(n).append("ABC")); 
    return result; 
} 

public static void permute(int n, List<String> result, int start, StringBuilder builder) { 
    if (builder.length() == n) { 
     // The String is complete so we add it to the combination list 
     result.add(builder.toString()); 
     return; 
    } 
    // Iterate from start to the length (included) of StringBuilder 
    for (int j = start; j <= builder.length(); j++) { 
     // Insert X at the position j 
     builder.insert(j, 'X'); 
     // Continue adding X but starting from next index 
     permute(n, result, j + 1, builder); 
     // Remove X at the position j 
     builder.deleteCharAt(j); 
    } 
} 

出力：

[XXABC, XAXBC, XABXC, XABCX, AXXBC, AXBXC, AXBCX, ABXXC, ABXCX, ABCXX] 

Answer 2

Bの右にあるすべての場所にCを反復する必要があります。次に、Bを右に1つ移動し、Cをもう一度右に移動します。それから、あなたはそれぞれのポジションAが取ることができるようにそれをしなければなりません。

ABCXX

ABXCX

ABXXC

AXBCX

AXBXC

AXXBC

XABCX

Answer 3

ここでは、結果を得るためにあなたのアルゴリズムを与えるPythonスクリプトです。あなたはそれがあなたが使うかもしれないどんな言語でもそれを適応させることができます。あなたはすでに文字列の一般的な順列の実装を知っているし、あなたはパフォーマンスの問題について気にしない場合は

#!/usr/bin/env python 

def comb(n, m, s): 
    global a 
    r = reversed(range(n)) 
    for i in r: 
     if m > 1: 
     comb(i, m-1,s + str(i)) 
     else: 
     b = a[:] 
     p = s + str(i) 

     for j in range(len(p)): 
      b[int(p[j])] = letters[j] 
     print(''.join(reversed(b))) 


letters = 'ABC' 
a = list('X' * 8); 
comb(8, 3, '') 

#ABCXXXXX 
#ABXCXXXX 
#ABXXCXXX 
#ABXXXCXX 
#ABXXXXCX 
#ABXXXXXC 
#AXBCXXXX 
#AXBXCXXX 
#AXBXXCXX 
#... 

Answer 4

、あなたはすべての順列のリストを表示して下さい

1. で実際に素早く、この問題を解決することができます"ABCXX"
2. 適切な条件でリストをフィルタリングします。

これは、Java 8+における一般的な順列方法

public static List<String> permutation(String s) { 

    /* 
    * # Given 
    * 1) permutation("A") = ["A"] 
    * 2) permutation("AB") = ["AB", "BA"] 
    * 3) permutation("AB") + "C" = ["AB", "BA"] + "C" = ["ABC", "BAC"] 
    * 
    * # Assumption 
    * - let s = any String 
    * - permutation(s) = a union list of permutation(s - x) + x for each letter x in s 
    * 
    * # Examples 
    * - permutation("ABC") = permutation("AB") + C U permutation("BC") + A U permutation("AC") + B 
    *    = ["AB","BA"] + C U ["BC", "CB"] + A U ["AC", "CA"] + B 
    *    = ["ABC","BAC"] U ["BCA","CBA"] U ["ACB", "CAB"] 
    *     
    * - permutation("ABCD") = permutation("ABC") + D U permutation("BCD") + A U permutation("CDA") + B U permutation("ABD") + C 
    * 
    * # Prove 
    * - There does not exist an element in permutation of "ABCD" where the last position is not in ("A","B","C","D") 
    * 
    */ 

    /********** Implement **********/ 

    if (s.length() == 1) { 
     return Arrays.asList(s); 
    } else { 
     List<String> rs = new ArrayList<>(); 
     for (int i=0; i<s.length(); i++) { 
      char x = s.charAt(i); 
      String theRest = s.substring(0, i) + s.substring(i+1, s.length()); 
      // following line means union of [permutation(theRest) + x] 
      rs.addAll(permutation(theRest).stream().map(e -> e + x).collect(Collectors.toList())); 
     } 
     return rs; 
    } 
    /********************************/ 
} 

の私のバージョンであり、ここで私はあなたの要件を満たすために順列をフィルタリングする方法です。

public static void main(String[] args) { 
    String conservedString = "ABC"; 
    int n = 5; 
    if (conservedString.length() > n) { 
     throw new RuntimeException("Invalid length of the conserved string: " + conservedString.length()); 
    } 
    String initialString = conservedString + Stream.iterate("X", x -> "X").limit(n - conservedString.length()).reduce("", (a,b) -> a+b); 
    List<String> result = permutation(initialString) 
     .stream() 
     .filter(x -> { 
      for (int i=0; i<conservedString.length()-1; i++) { 
       if (x.indexOf(conservedString.charAt(i)) > x.indexOf(conservedString.charAt(i+1))) { 
        return false; 
       } 
      } 
      return true; 
     }) 
     .peek(System.out::println) 
     .collect(Collectors.toList()); 
} 

パフォーマンスにもかかわらずこのアプローチの1つの利点は、それが容易に理解でき、メンテナンスが容易であるということです。他の種類のパターンが必要な場合は、フィルタロジックを編集するだけです。