ぜんはいちアルゴリズム
3372 ワード
ディクショナリ・シーケンスのアルゴリズムは次のとおりです.
Pを1～nの全配列とする:p=p 1 p 2…pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1)右端から右端より小さい最初の数字の番号j(jは左端から計算)を探し出す,すなわちj=max{i|pi
2)pjの右側の数字の中から,pjより大きい数の中で最も小さい数字pk,すなわちk=max{i|pi>pj}(右側の数は右から左へ増加し,
したがってkはpjより大きいすべての数字の中でシーケンス番号が最大である)
3)交換pi,pk
4)さらにpj+1を……pk-1pkpk
+1 pn逆転配列p'=p 1 p 2.....pj-1pjpn.....pk+1pkpk-1.....pj+1,これが配列pの次の配列である.
例えば、839647521は、数字1〜9の1つの配列である.次の配列を生成するには、右から左に配列の最初の右より小さい数字4 839647521を見つけます.
この数字の後の数字の中で4より大きい数の中で最も小さい1つの5 839647521を探し出して5と4を交換します839657421は7421を逆転します839651247
したがって、839647521の次の配列は839651247である.839651247の次の配列は839651274である.
フル配列再帰アルゴリズム実装
集合が{a,b,c}である場合、この集合中の要素のすべての配列は{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,(c,b,a)}であり、n個の要素がn個共有されていることは明らかである.与えられた集合が{a,b,c,d}である場合、以下に示す単純なアルゴリズムを用いて、そのすべての配列、すなわち集合(a,b,c,d)のすべての配列を生成することができる.
(1)aで始まる後に続く(b,c,d)の並び
(2)bで始まる後に続く(a,c,d)の並び
(3)cで始まる後に続く(a,b,d)の並び
(4)dで始まると(a,b,c)の配列に続くのは明らかに再帰的な考え方であり,以下の実現を得た.
Pを1～nの全配列とする:p=p 1 p 2…pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1)右端から右端より小さい最初の数字の番号j(jは左端から計算)を探し出す,すなわちj=max{i|pi
2)pjの右側の数字の中から,pjより大きい数の中で最も小さい数字pk,すなわちk=max{i|pi>pj}(右側の数は右から左へ増加し,
したがってkはpjより大きいすべての数字の中でシーケンス番号が最大である)
3)交換pi,pk
4)さらにpj+1を……pk-1pkpk
+1 pn逆転配列p'=p 1 p 2.....pj-1pjpn.....pk+1pkpk-1.....pj+1,これが配列pの次の配列である.
例えば、839647521は、数字1〜9の1つの配列である.次の配列を生成するには、右から左に配列の最初の右より小さい数字4 839647521を見つけます.
この数字の後の数字の中で4より大きい数の中で最も小さい1つの5 839647521を探し出して5と4を交換します839657421は7421を逆転します839651247
したがって、839647521の次の配列は839651247である.839651247の次の配列は839651274である.
public static void main(String[] args) {
long l1 = System.currentTimeMillis();
System.out.println(" n :");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] arry = new int[n];
for (int i = 0; i < arry.length; i++) {
arry[i] = i + 1;
}
System.out.println(Arrays.toString(getInt(arry)));
do {
System.out.println(Arrays.toString(getInt(arry)));
} while (next(arry));
long l2 = System.currentTimeMillis();
System.out.print(" " + (l2 - l1) + " ");
}
private static int[] getInt(int[] arry) {
int[] arry1 = new int[arry.length];
System.arraycopy(arry, 0, arry1, 0, arry.length);
return arry1;
}
private static boolean next(int[] arry) {
int pos1 = -1;
int pos2 = -1;
// ， ， pos1
for (int i = arry.length - 1; i > 0; i--) {
if (arry[i - 1] < arry[i]) {
pos1 = i - 1;
break;
}
}
if (pos1 < 0) {
return false;
}
// pos1 ， ，
for (int i = arry.length - 1; i > pos1; i--) {
if (arry[i] > arry[pos1]) {
pos2 = i;
swap(arry, pos2, pos1);
reserve(arry, pos1 + 1, arry.length - 1);
break;
}
}
if (pos2 < 0) {
return false;
}
return true;
}
/**
*
* i j , 123，i=0,j=2, 321
*
* @param arry
* @param i
* @param j
*/
private static void reserve(int[] arry, int i, int j) {
for (; i <= j; i++, j--) {
swap(arry, i, j);
}
}
/**
* i j
*
* @param array
* @param i
* @param j
*/
private static void swap(int[] array, int i, int j) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}フル配列再帰アルゴリズム実装
集合が{a,b,c}である場合、この集合中の要素のすべての配列は{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,(c,b,a)}であり、n個の要素がn個共有されていることは明らかである.与えられた集合が{a,b,c,d}である場合、以下に示す単純なアルゴリズムを用いて、そのすべての配列、すなわち集合(a,b,c,d)のすべての配列を生成することができる.
(1)aで始まる後に続く(b,c,d)の並び
(2)bで始まる後に続く(a,c,d)の並び
(3)cで始まる後に続く(a,b,d)の並び
(4)dで始まると(a,b,c)の配列に続くのは明らかに再帰的な考え方であり,以下の実現を得た.
public static void main(String[] args) {
char[] data={'a','b','c'};
permutation(data,0,data.length-1);
}
private static void permutation(char[] data, int start, int end) {
int i,j;
if(start==end){
for(i=0;i<=end;i++){
System.out.print(data[i]);
}
System.out.println();
}else{
for(j=start;j<=end;j++){
swap(data,j,start);
permutation(data, start+1, end);
swap(data,j,start);
}
}
}
private static void swap(char[] data,int j, int start) {
char temp = data[j];
data[j] = data[start];
data[start] =temp;
}