Cobbage 发表于4年前

• 发表于 4年前
• 阅读 70
• 收藏 0
• 评论 0

``````public static void recursive(char[] test_array, int start, int end) {
if (start == end) {
for (int i = 0; i <= end; i++) {
System.out.print(test_array[i] + " ");
}
System.out.println();
} else {
for (int j = start; j <= end; j++) {
char temp = test_array[start];
test_array[start] = test_array[j];
test_array[j] = temp;

recursive(test_array, start + 1, end);

temp = test_array[start];
test_array[start] = test_array[j];
test_array[j] = temp;
}
}
}``````

``````public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
permuteUnique(num, 0, result);
return result;
}

private void permuteUnique(int[] num, int start, ArrayList<List<Integer>> result) {

if (start >= num.length ) {
ArrayList<Integer> item = convertArrayToList(num);
}

for (int j = start; j <= num.length-1; j++) {
if (containsDuplicate(num, start, j)) {
swap(num, start, j);
permuteUnique(num, start + 1, result);
swap(num, start, j);
}
}
}

private ArrayList<Integer> convertArrayToList(int[] num) {
ArrayList<Integer> item = new ArrayList<Integer>();
for (int h = 0; h < num.length; h++) {
}
return item;
}

private boolean containsDuplicate(int[] arr, int start, int end) {
for (int i = start; i <= end-1; i++) {
if (arr[i] == arr[end]) {
return false;
}
}
return true;
}

private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}``````

``````public class Solution {
public String getPermutation(int n, int k) {
k--;//to transfer it as begin from 0 rather than 1

List<Integer> numList = new ArrayList<Integer>();
for(int i = 1; i<= n; i++)

int factorial = 1;
for(int i = 2; i < n; i++)
factorial *= i;

StringBuilder res = new StringBuilder();
int times = n-1;
while(times>=0){
int indexInList = k/factorial;
res.append(numList.get(indexInList));
numList.remove(indexInList);

k = k%factorial;//new k for next turn
if(times!=0)
factorial = factorial/times;//new (n-1)!

times--;
}

return res.toString();
}
}``````

如果从前向后应该是的i<=m

``````static void combine( int a[],int n,int m,int b[] )
{
for(int i=n; i>=m; i--)
{
b[m-1] = a[i-1];
if (m > 1)
combine(a,i-1,m-1,b);
else
{
System.out.println(Arrays.toString(b));
}
}
}``````

2.接着倒叙查找如果有大于前一个的位置（这说明有下一个排列）

3.在上个可能的位置后面查找可能有最小的大于当前的值（这个是存在排列的一个最小的序）

4.交换位置后一位后面是（递减的，要反转变成递增的）这样得到新列的最小序

5.如果全部变成了递增额则排列结束了

``````public static void main(String[] args) {

// TODO 自动生成方法存根
WordBook a = new WordBook();
Scanner input = new Scanner(System.in);
System.out.print("请输入要排列的元素有多少种:");
int count = input.nextInt();
int[] p = new int[count];
for (int i = 1; i <= p.length; i++) {
p[i - 1] = i;
}
boolean con;
long start=System.currentTimeMillis();
do {
a.pr(p);// 输出排列p
con = a.next(p);// 求出按字典序排列的下一个排列p
} while (con);
System.out.println(System.currentTimeMillis()-start);
}

public int indexof(int[] n) {
int index = -1;
for (int i = n.length - 1; i >= 1; i--) {
if (n[i - 1] < n[i]) {
index = i - 1;
break;
}
}
return index;
}

public int indexmin(int ini, int[] n) {
int index = n.length - 1;
int min = n[ini + 1];
for (int i = ini + 1; i < n.length; i++) {
if (n[i] <= min && n[i] > n[ini]) {
min = n[i];
index = i;
}
}
return index;
}

public void swap(int index1, int index2, int[] n) {
int temp;
temp = n[index1];
n[index1] = n[index2];
n[index2] = temp;
}

public void oppositeDirection(int index1, int[] n) {
for (int i = index1 + 1, j = n.length - 1, k = 0, temp; k <= (n.length - i) / 2; i++, j--, k++) {
temp = n[i];
n[i] = n[j];
n[j] = temp;
}
}

public boolean next(int[] n) {
int index1 = indexof(n);
if (index1 == -1) {
return false;
}
int index2 = indexmin(index1, n);
swap(index1, index2, n);
oppositeDirection(index1, n);
return true;
}

public void pr(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + "  ");
}
System.out.println();
}``````

组合：网上找的那个10排列的

``````//按照网上的10转换
//输出有10的位置第一次位置
//然后调整为01
//10左边的移动到左边
static void combine2(int[]a,int n,int m,int[] b){
for(int i=0;i<m;i++)
b[i]=1;
do{
printArray(b,a);
}while(getFirstFlage(b,n,m)!=-1);
}

static int getFirstFlage(int[]b,int n,int m){
int count=0;
for(int i=0;i<n-1;i++){

if(b[i]==1&&b[i+1]==0){
//交换位置
b[i]=0;
b[i+1]=1;
//移动
for(int j=0;j<count;j++){
b[j]=1;
}
for(int k=count;k<i;k++)
b[k]=0;
// System.out.println(count+"=="+Arrays.toString(b));
return i;
}else if(b[i]==1){
count++;
}
}
return -1;
}
static void printArray(int[]b,int[]a){
for(int i=0;i<b.length;i++){
if(b[i]==1)
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {

int[] a=new int[]{1,2,3,4,5,6,7,8};
int[] b=new int[8];
combine2(a,a.length,3,b);
//combine(a,a.length,2,b);
//System.out.println("总的个数："+k);
}``````

Cobbage

×