1

私の質問は、整数の入力を指定して順列を出力する再帰的な方法に関するものです。各整数は、電話のキーパッドのような一連の文字を表します。

したがって、セットは次のようになります。

1: {}
2: {"A", "B", "C"}
3: {"D", "E", "F"}
4: {"G", "H", "I"}
etc...

一連の数値を指定すると、文字のすべての順列が出力されるコードを作成する必要があります。

したがって、123 を入力すると、AD、AE、AF、BD、BF、CD、CE、CF が出力されます。

疑似コードが好まれます。私は Java に少しだけ精通していますが、どんな助けも歓迎します。

この質問の仕方についてフィードバックをお寄せください。ここに適切に投稿する方法がまだわかりません。

4

2 に答える 2

0

でそれを行う1つの方法を次に示しますF#。

open System
open System.Collections.Generic

let pad = new Dictionary<int, string>()
pad.Add(2, "A,B,C")
pad.Add(3, "D,E,F")
pad.Add(4, "G,H,I")

let permutations = new List<string>()

let rec permute(digits: int list, alphas: string list) =    
    if List.length digits > 0 && List.length alphas = 0 then
        permute(digits, ["#"] |> List.append (pad.[digits.[0]].Split([|','|]) |> List.ofArray))
    else
        match alphas with
        | [_] ->
            match digits with
            | h::t -> permute(t, [])
            | _ -> ()
        | h::t ->
            for i = 0 to List.length alphas - 2 do
                permutations.Add(h + alphas.[i])
            for j = 1 to List.length digits - 1 do
                let others = pad.[digits.[j]].Split([|','|])
                for o in others do
                    permutations.Add(h + o)
            permute(digits, t)
        | _ -> ()

permute([2;3;4;], [])

seq { 
    for o in permutations do 
        yield o
        yield o.[1].ToString() + o.[0].ToString()
}
|> Seq.distinct
|> Seq.sort 
|> Seq.iter(fun s -> Console.WriteLine(s))
;;

出力

[2; 3; 4]
[]


[2; 3; 4]
[A; B; C; ... ]

AA
AB
AC
AD
AE
AF
AG
AH
AI

[2; 3; 4]
[B; C; #]

BB
BC
BD
BE
BF
BG
BH
BI

[2; 3; 4]
[C; #]

CC
CD
CE
CF
CG
CH
CI

[2; 3; 4]
[#]


[3; 4]
[]


[3; 4]
[D; E; F; ... ]

DD
DE
DF
DG
DH
DI

[3; 4]
[E; F; #]

EE
EF
EG
EH
EI

[3; 4]
[F; #]

FF
FG
FH
FI

[3; 4]
[#]


[4]
[]


[4]
[G; H; I; ... ]

GG
GH
GI

[4]
[H; I; #]

HH
HI

[4]
[I; #]

II

[4]
[#]


[]
[]

AA
AB
AC
AD
AE
AF
AG
AH
AI
BA
BB
BC
BD
BE
BF
BG
BH
BI
CA
CB
CC
CD
CE
CF
CG
CH
CI
DA
DB
DC
DD
DE
DF
DG
DH
DI
EA
EB
EC
ED
EE
EF
EG
EH
EI
FA
FB
FC
FD
FE
FF
FG
FH
FI
GA
GB
GC
GD
GE
GF
GG
GH
GI
HA
HB
HC
HD
HE
HF
HG
HH
HI
IA
IB
IC
ID
IE
IF
IG
IH
II
于 2013-05-01T10:17:04.287 に答える
0

2 つ取り、順列Setの を返す非再帰関数を使用できます。Set

private Set<String> getPermutations(Set<String> a, Set<String> b){
...
}

次に、再帰関数を使用できます

public Set<String> recursivePermutations(List<Set<String>> sets){
    if(sets.size() ==2){
        return getPermutations(sets.get(0), sets.get(1));
    }else{
        return getPermutations(sets.get(0),recursivePermutations(sets.sublist(1,sets.size()-1));
    }
}

リストに要素が 1 つしかない場合に安全なガードを追加しCollection、リストが本当に必要ない場合にも使用することをお勧めします。

編集

再帰の背後にある主な考え方は、非再帰的な方法を適用できる単純なケース (2 つのセットしかない場合) と、縮小されたサイズの問題に関数を再度適用する必要がある場合の再帰的なケースの 2 つのケースを持つことです。 .

私の例では、2 つ以上のセットがある場合、同じ関数を再帰的に再適用しますが、セットの数を減らします (関数は最初の要素と残りのセットに適用されます)。

n最初にセットのリストに関数を適用すると想像してください。関数を 2 回目に適用すると、 のリストが表示n-1され、ケースに到達するまで続きますn=2。この場合、単純なケースなので、再帰を使用する必要はありません。

于 2013-04-30T13:14:25.367 に答える