【微软2014实习生及秋令营技术类职位在线測试】题目2 : K-th string
Description
Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K-th string according to the dictionary order. If such a string doesn’t exist, or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s, we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10000), the number of test cases, followed by the input data for each test case.
Each test case is 3 integers separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0), K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s, and K stands for the K-th of string in the set that needs to be printed as output.
Output
For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.
3 2 2 2 2 2 7 4 7 47例子输出
0101 Impossible 01010111011思路：带有反复字符的全排列问题
import java.lang.String;
import java.lang.StringBuilder;
import java.net.Inet4Address;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
public class Permutation {
static int sum ;
public static void main(String[] args)
{
int T ;
Scanner jin = new Scanner(System.in);
T = jin.nextInt();
while(T-- > 0)
{
int N, M, K;
StringBuilder stringBuilder = new StringBuilder();
N = jin.nextInt();M = jin.nextInt();K = jin.nextInt();
if (!((M+N) >= 2 && (N+M) <= 33)) {
System.out.println("Impossible");
continue;
}
if(N < 0 || M < 0)
{
System.out.println("Impossible");
continue;
}
for (int i = 0; i < N; i++) {
stringBuilder.append('0');
}
for (int i = 0; i < M; i++) {
stringBuilder.append('1');
}
sum = 0;
permutation(stringBuilder.toString().toCharArray(), 0, stringBuilder.length()-1, K);
if (sum < K) {
System.out.println("Impossible");
}
}
}
public static void permutation(char[] str, int start, int end, int K) {
if (start == end) {
sum++;
//System.out.print(sum);
//System.out.print(" ");
//System.out.print(new String(str));
//System.out.print(" ");
if (sum == K) {
System.out.println(new String(str));
return ;
}
}
else {
for (int i = start; i <= end; i++) {
if(!Isduplicated(str, start, i))
{
char tmp = str[start];
str[start] = str[i];
str[i] = tmp;
permutation(str, start+1, end, K);
tmp = str[start];
str[start] = str[i];
str[i] = tmp;
}
}
}
}
public static boolean Isduplicated(char[] ch, int start, int end) {
for (int i = start; i < end; i++) {
if (ch[i] == ch[end]) {
return true;
}
}
return false;
}
}
