組み合わせの作り方

質問

整数x～yを１回ずつ含んだ配列を作りたいんですが、どうすればいいでしょうか？何かアルゴリズムってありましたっけ？
例えば1～3では

123
132
213
231
312
321

となります

回答No.2

zozy · ベストアンサー

少々、適当なアルゴリズムですが、一応動くので参考にしてください。
無駄があるので、良いアルゴリズムではありませんが...

public class Main {
public static void main(String[] args) {
Test test = new Test(4);
}
}
class Test{
// 組み合わせの整数を格納する配列
int[] array;
// 整数の種類の数(整数の桁)
int digit;
// 配列のインデックス
int count = 0;
public Test(int digit){
// arrayの長さ
int arrayLength = 1;
// 探索する範囲
int searchLength = 1;
int tmp;
// 局所変数digitをフィールド変数digitへ代入
this.digit = digit;
for(int i=1;i<=digit;i++){
// arrayの長さを計算(digit!)
// 例.digit=4なら4*3*2*1=24
arrayLength *= i;
// 探索する範囲を計算((digit+1)のdigit乗)
// 例.digit=4なら5の4乗=3125
searchLength *= (digit + 1);
}
// arrayを生成
array = new int[arrayLength];
// 組み合わせの数を探索し、結果をarrayへ代入
for(int i=1;i<searchLength;i++){
tmp = ternary(i);
if(tmp > 0){
array[count] = tmp;
System.out.println(array[count]);
count++;
}
}
// arrayの内容を表示
for(int i:array){
System.out.println(i);
}
}
// 10進数からdigit進数に変換
// 例.digit=4なら4進数へ変換
private int ternary(int num){
String result = "";
while(num > 0){
result += num % (digit + 1);
num /= (digit + 1);
}
result = new StringBuffer(result).reverse().toString();
// 組み合わせの数に相応しければそのまま
// 相応しくなければ-1を返す
// -1の場合arrayには代入されない
if(checkRepetition(result)){
return Integer.parseInt(result);
}else{
return -1;
}
}
// 0を含んでいたり、数字が重なってないか判定
private boolean checkRepetition(String str){
boolean repetition = true;
// 桁が足りなくないか
if(str.length() < digit){
repetition = false;
}
// 0を含んでないか
if(repetition){
for(int i=0;i<str.length();i++){
if(str.charAt(i) == '0'){
repetition = false;
break;
}
}
}
// 数字が重なってないか
if(repetition){
ESC:
for(int i=0;i<str.length()-1;i++){
for(int j=i+1;j<str.length();j++){
if(str.charAt(i) == str.charAt(j)){
repetition = false;
break ESC;
}
}
}
}
return repetition;
}
}

回答No.1

Tacosan

よくあるパターンは再帰を使う.
配列を 2個使っていいなら「階乗進法」という謎の技もある.