10

このサイトにはいくつかの同様の質問があり、役に立ちましたが、私はこの問題を完全に突き止めることができないので、これが繰り返されないことを願っています.

これは、一連の文字 [A、B、C] の配列があり、再帰を使用してすべての順列を (繰り返しで) 取得する必要がある宿題です。私が持っているコードはこれを行います：

char[] c = {'A', 'B' , 'C'};

public void printAll(char[] c, int n, int k) {
    if (k == n) {
      System.out.print(c);
      return;
    }
    else {   
      for (int j = 0; j<n; j++) {
        for (int m = 0; m<n; m++) {
           System.out.print(c[k]); 
           System.out.print(c[j]); 
           System.out.print(c[m] + "\r\n");
        }
      }
    }        
    printAll(c, n, k+1);    
}

ただし、パラメーター n は出力の長さを定義する必要があるため、この関数は長さ 3 のすべての順列を出力しますが、長さ 2 の順列を実行することはできません。そして、かなり単純な問題のように見える問題を解決できないことで、私は自分自身に腹を立てています。

4

4 に答える 4

9

私の理解が正しければ、一連の文字cと希望の長さが与えられますn。

技術的には、繰り返しを伴う順列のようなものはありません。nからの文字を含む長さのすべての文字列が必要だと思いますc。

次の方法で実行できます。

to generate all strings of length N with letters from C
 -generate all strings of length N with letters from C
     that start with the empty string.

to generate all strings of length N with letters from C
   that start with a string S
 -if the length of S is N
  -print S
 -else for each c in C
  -generate all strings of length N with letters from C that start with S+c

コード内:

printAll(char[] c, int n, String start){
  if(start.length >= n){
    System.out.println(start)
  }else{
    for(char x in c){ // not a valid syntax in Java
      printAll(c, n, start+x);
    }
  }
}
于 2012-10-31T12:42:13.843 に答える
3

私はこの Java の繰り返しによる順列の実現を使用します。A~(n,m): n = 配列の長さ、m = k。m は n より大きくても小さくてもかまいません。

public class Permutations {


    static void permute(Object[] a, int k, PermuteCallback callback) {
        int n = a.length;

        int[] indexes = new int[k];
        int total = (int) Math.pow(n, k);

        Object[] snapshot = new Object[k];
        while (total-- > 0) {
            for (int i = 0; i < k; i++){
                snapshot[i] = a[indexes[i]];
            }
            callback.handle(snapshot);

            for (int i = 0; i < k; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
    }

    public static interface PermuteCallback{
        public void handle(Object[] snapshot);
    };

    public static void main(String[] args) {
        Object[] chars = { 'a', 'b', 'c', 'd' };
        PermuteCallback callback = new PermuteCallback() {

            @Override
            public void handle(Object[] snapshot) {
                for(int i = 0; i < snapshot.length; i ++){
                    System.out.print(snapshot[i]);
                }
                System.out.println();
            }
        };
        permute(chars, 8, callback);
    }

}

出力例は

aaaaaaaa
baaaaaaa
caaaaaaa
daaaaaaa
abaaaaaa
bbaaaaaa
...
bcdddddd
ccdddddd
dcdddddd
addddddd
bddddddd
cddddddd
dddddddd
于 2016-10-18T06:49:35.407 に答える
1

アイデアがありました。非表示の文字 (非表示の H) [A、B、C、H] を追加し、そのすべての固定長順列を実行した場合はどうなるでしょうか (その方法を知っていると言っていました)。次に、それを読み取ると、隠し文字で停止します。たとえば、[B,A,H,C] は (B,A) になります。

うーん、[B,H,A,C] は [B,H,C,A] と同じですが、作成したものを追跡する必要があるという欠点があります。

于 2012-10-31T12:17:20.803 に答える