アルゴリズム設計と分析:2-9配列の辞書順問題
15312 ワード
2-9の辞書順の問題
問題の説明
n個の要素{1,2,...,n}はn!個の異なる配列.これをn!個の配列を辞書順に並べ、0,1,...,n!-1.各配列の番号は、辞書の順序値です.例えば、n=3の場合、6つの異なる配列の辞書シーケンス値は以下のようになる.
ディクショナリ順序値
0
1
2
3
4
5
整列
123
132
213
231
312
321
n,およびn個の要素{1,2,...,n}の配列を与え,この配列の辞書順値と辞書順に配列された次の配列を計算した.
ぜんはいち
Java: version-1
Input & Output
数学的導出
Java: version-2
Input & Output
Reference
王暁東『コンピュータアルゴリズム設計と分析』(第3版)P 45
問題の説明
n個の要素{1,2,...,n}はn!個の異なる配列.これをn!個の配列を辞書順に並べ、0,1,...,n!-1.各配列の番号は、辞書の順序値です.例えば、n=3の場合、6つの異なる配列の辞書シーケンス値は以下のようになる.
ディクショナリ順序値
0
1
2
3
4
5
整列
123
132
213
231
312
321
n,およびn個の要素{1,2,...,n}の配列を与え,この配列の辞書順値と辞書順に配列された次の配列を計算した.
ぜんはいち
Java: version-1
import java.util.*;
public class Main {
private static int n;
private static String inputStr;
private static char[] strToChar = new char[1000];
private static String tmpPerm;
private static Set permSet = new HashSet<>();
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(true){
permSet.clear();
System.out.println("Please input the length of string: ");
n = input.nextInt();
System.out.println("Please input a digit string: ");
inputStr = input.next();
System.out.println("-------------------------");
strToChar = inputStr.toCharArray();
permutate(strToChar, 0, n-1);
int i=0;
int size = permSet.size();
String[] numbers = new String[size];
Iterator iterator = permSet.iterator();
while (iterator.hasNext()){
String value = iterator.next();
numbers[i++] = value;
}
Arrays.sort(numbers);
for(i=0; iif(numbers[i].equals(inputStr)) {
System.out.println("Permutation at: "+i);
if(i+1 < size)
System.out.println("Next permutation: "+numbers[i+1]);
else
System.out.println("There is no permutation after: "+numbers[i]);
}
}
System.out.println("------------------------------------------");
}
}
private static void permutate(char[] charList, int k, int m){
if(k == m){
tmpPerm = String.valueOf(charList);
permSet.add(tmpPerm);
return;
}
for(int i=k; i<=m; i++){
swap(charList, k, i);
permutate(charList, k+1, m);
swap(charList, k, i);
}
}
private static void swap(char[] charList, int k, int i){
char temp;
temp = charList[k];
charList[k] = charList[i];
charList[i] = temp;
}
} Input & Output
Please input the length of string:
8
Please input a digit string:
26458173
-------------------------
Permutation at: 8227
Next permutation: 26458317
------------------------------------------
Please input the length of string:
8
Please input a digit string:
87654321
-------------------------
Permutation at: 40319
There is no permutation after: 87654321
------------------------------------------
Please input the length of string:
8
Please input a digit string:
87654312
-------------------------
Permutation at: 40318
Next permutation: 87654321
------------------------------------------
Please input the length of string:
6
Please input a digit string:
231456
-------------------------
Permutation at: 144
Next permutation: 231465
------------------------------------------
Please input the length of string: 数学的導出
Java: version-2
import java.util.Scanner;
public class Main{
private static boolean hasNextPerm = true;
public static void main(String[] args){
int n;
Scanner input = new Scanner(System.in);
while(true){
System.out.println("Input the number of digits:");
n = input.nextInt();
int[] numbers = new int[n];
System.out.println("Input digits:");
for(int i=0; iint rank = dictRank(numbers, n);
nextPermutation(numbers, n);
System.out.println("Permutation at: "+rank);
if(hasNextPerm) {
System.out.print("Next Permutation: ");
}
else
System.out.print("There is no permutation after: ");
for (int i = 0; i < n; i++)
System.out.print(numbers[i]);
System.out.println();
System.out.println("-------------------------------------");
}
}
/*
2 6 4 5 8 1 7 3 ？
1 P(i-1) < P(i)
2 6 4 4 5 8 1
//
private static void nextPermutation(int[] numbers, int n){
int min=0, max=n-1, i, j;
for(i=n-1; i>0; i--){ //1
if(numbers[i-1] < numbers[i]){
min = i-1;
break;
}
}
if(i == 0)
hasNextPerm = false;
else{
hasNextPerm = true;
for(j=n-1; j>=0; j--){ //2
if(numbers[j] > numbers[min]){
max = j;
break;
}
}
swap(numbers, min, max); //3
reverse(numbers, min+1, n-1); //4
}
}
//
private static void reverse(int[] numbers, int from, int to){
int[] tmp = new int[to+1];
for(int h=from; h<=to; h++)
tmp[h] = numbers[h];
for(int h=from; h<=to; h++)
numbers[h] = tmp[to+from-h];
}
//
private static void swap(int[] numbers, int min, int max){
int tmp = numbers[min];
numbers[min] = numbers[max];
numbers[max] = tmp;
}
/*
2 6 4 5 8 1 7 3
total=0；
2 1 ， total+=1*7！；
6 4 ， total+=4*6！；
4 2 ， total+=2*5！；
5 2 ， total+=2*4！；
8 3 ， total+=3*3！；
1 0 ， total+=0*2！；
7 1 ， total+=1*1！；
3 ；
*/
//
private static int dictRank(int[] numbers, int n){
int count;
int total = 0;
for(int i=0; i1 ; i++){
count = 0;
for(int j=i+1; jif(numbers[j] < numbers[i])
count++;
total += count*factorial(n-i-1);
}
return total;
}
//
private static int dictRank2(int[] numbers, int n){
int count;
int sum = 0;
for(int i=0; i1; i++){
count = numbers[i] - 1;
for(int j=0; jif(numbers[j] < numbers[i])
count--;
sum += count*factorial(n-i-1);
}
return sum;
}
//n
private static int factorial(int n){
int total = 1;
for(int i=1; i<=n; i++){
total *= i;
}
return total;
}
} Input & Output
Input the number of digits:
8
Input digits:
2 6 4 5 8 1 7 3
Permutation at: 8227
Next Permutation: 26458317
-------------------------------------
Input the number of digits:
8
Input digits:
8 7 6 5 4 3 2 1
Permutation at: 40319
There is no permutation after: 87654321
-------------------------------------
Input the number of digits:
8
Input digits:
8 7 6 5 4 3 1 2
Permutation at: 40318
Next Permutation: 87654321
-------------------------------------
Input the number of digits:
6
Input digits:
2 3 1 4 5 6
Permutation at: 144
Next Permutation: 231465
-------------------------------------
Input the number of digits:Reference
王暁東『コンピュータアルゴリズム設計と分析』(第3版)P 45