从n个数中取出m个数的所有组合。
package algorithm;
//组合算法
//本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
//代表的数被选中，为0则没选中。
//首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
//然后从左到右扫描数组元素值的"10"组合，找到第一个"10"组合后将其变为
//"01"组合，同时将其(在本算法中具体指i的位置)左边的所有"1"全部移动到数组的最左端。
//当第一个"1"移动到数组的m-n的位置，即n个"1"全部移动到最右端时，就得
//到了最后一个组合。
//例如求5中选3的组合：
//1 1 1 0 0 //1,2,3
//1 1 0 1 0 //1,2,4
//1 0 1 1 0 //1,3,4
//0 1 1 1 0 //2,3,4
//1 1 0 0 1 //1,2,5
//1 0 1 0 1 //1,3,5
//0 1 1 0 1 //2,3,5
//1 0 0 1 1 //1,4,5
//0 1 0 1 1 //2,4,5
//0 0 1 1 1 //3,4,5
import java.util.ArrayList;
import java.util.List;
/**
* java 代码实现组合的算法
* 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1
* @author dubensong
*
*/
public class AssemblyDemo {
/**
* @param a:组合数组
* @param m:生成组合长度
* @return :所有可能的组合数组列表
*/
private List<int[]> combination(int[] a, int m) {
AssemblyDemo c = new AssemblyDemo();
List<int[]> list = new ArrayList<int[]>();
int n = a.length;
boolean end = false; // 是否是最后一种组合的标记
// 生成辅助数组。首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
int[] tempNum = new int[n];
for (int i = 0; i < n; i++) {
if (i < m) {
tempNum[i] = 1;
} else {
tempNum[i] = 0;
}
}
printVir(tempNum);// 打印首个辅助数组
list.add(c.createResult(a, tempNum, m));// 打印第一种默认组合
int k = 0;//标记位
while (!end) {
boolean findFirst = false;
boolean swap = false;
// 然后从左到右扫描数组元素值的"10"组合，找到第一个"10"组合后将其变为"01"
for (int i = 0; i < n; i++) {
int l = 0;
if (!findFirst && tempNum[i] == 1) {
k = i;
findFirst = true;
}
if (tempNum[i] == 1 && tempNum[i + 1] == 0) {
tempNum[i] = 0;
tempNum[i + 1] = 1;
swap = true;
for (l = 0; l < i - k; l++) { // 同时将其左边的所有"1"全部移动到数组的最左端。
tempNum[l] = tempNum[k + l];
}
for (l = i - k; l < i; l++) {
tempNum[l] = 0;
}
if (k == i && i + 1 == n - m) {//假如第一个"1"刚刚移动到第n-m+1个位置,则终止整个寻找
end = true;
}
}
if (swap) {
break;
}
}
printVir(tempNum);// 打印辅助数组
list.add(c.createResult(a, tempNum, m));// 添加下一种默认组合
}
return list;
}
// 根据辅助数组和原始数组生成结果数组
public int[] createResult(int[] a, int[] temp, int m) {
int[] result = new int[m];
int j = 0;
for (int i = 0; i < a.length; i++) {
if (temp[i] == 1) {
result[j] = a[i];
System.out.println("result[" + j + "]:" + result[j]);
j++;
}
}
return result;
}
// 打印整组数组
public void print(List<int[]> list) {
System.out.println("具体组合结果为:");
for (int i = 0; i < list.size(); i++) {
int[] temp = (int[]) list.get(i);
for (int j = 0; j < temp.length; j++) {
java.text.DecimalFormat df = new java.text.DecimalFormat("00");//将输出格式化
System.out.print(df.format(temp[j]) + " ");
}
System.out.println();
}
}
// 打印辅助数组的方法
public void printVir(int[] a) {
System.out.println("生成的辅助数组为：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
System.out.println();
}
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5 ,6,7,8,9}; // 整数数组
int m = 5; // 待取出组合的个数
AssemblyDemo c = new AssemblyDemo();
List<int[]> list = c.combination(a, m);
c.print(list);
System.out.println("一共" + list.size() + "组!");
}
}
打印出n个数的所有排列
package exec.basic;
public class Paixu {
public static void main(String[] args) throws Exception {
char[] para = {1,2,3,4,5,6,7,8,9};
for(int i=0;i<para.length;i++)
para[i]+=48;
paixu(para,para.length,0);
}
private static void paixu(char[] array, int n, int k) {
if (n == k) {
char[] out = new char[n];
for (int i = 0; i < array.length; i++) {
out[i] = array[i];
}
System.out.println(new String(out));
} else {
for (int i = k; i < n; i++) {
swap(array, k, i);
paixu(array, n, k + 1);
swap(array, i, k);
}
}
}
private static void swap(char[] a, int x, int y) {
char temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
1,2,2,3,4,5，第三位不能是4,35不想连。
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 1,2,2,3,4,5 排列
* 不能有重复,比如 122345和122345是相同的
* 4不能再第三位,比如：124325
* 3和5不能挨着,比如：142235和142253
* @author wdai
*
*/
public class TestCombination {
public static void main(String[] args){
Integer[] arrSource={1,2,2,3,4,5};
combination(Arrays.asList(arrSource),new ArrayList<Integer>());
}
/**
* 递归方法
* @param listSource
* @param listLeft
*/
public static void combination(List<Integer> listSource,List<Integer> listLeft){
int index=listLeft.size()-1;
if(index==2&&listLeft.get(index)==4)
return;
if(index>0){
if(listLeft.get(index)==3&&listLeft.get(index-1)==5)
return;
if(listLeft.get(index)==5&&listLeft.get(index-1)==5)
return;
}
if(listSource.size()==0){
for(int n:listLeft)
System.out.print(n);
System.out.println();
return;
}
for(int i=0;i<listSource.size();i++){
int currentNum=listSource.get(i);
List<Integer> newListSource=new ArrayList<Integer>(listSource);
List<Integer> newListLeft=new ArrayList<Integer>(listLeft);
newListLeft.add(currentNum);
newListSource.remove(i);
if(i<listSource.size()-1&&listSource.get(i+1)==currentNum)
i++;
combination(newListSource,newListLeft);
}
}
}
比较字符串是否相等。不区分大小写，不区分顺序。
比如“ａ”与“Ａ”相等。比如“ａｂｃ”与“ｂａｃ”相等。
package exec.basic;
import java.util.Scanner;
public class StrEqual {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String str2=sc.nextLine();
str=str.toLowerCase();
str2=str2.toLowerCase();
if(str.length()!=str2.length()){
System.out.println("两字符串不等。");
System.exit(0);
}
int arr[]=new int[26];
for(int i=0;i<arr.length;i++)
arr[i]=0;
for(int i=0;i<str.length();i++){
char ch=str.charAt(i);
int j=ch-97;
arr[j]+=1;
}
for(int i=0;i<str.length();i++){
char ch=str2.charAt(i);
int j=ch-97;
arr[j]-=1;
}
int count=0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0)
count++;
}
if(count==26)
System.out.println("str和str2相等。");
else
System.out.println("str和str2不等。");
}
}
螺旋输出数组中的元素：
package test;
public class Test {
int [][]arr=new int[9][9];
int i=0;
int j=0;
int num=1;
public void spire(){
if(arr.length!=1){
Direction dir=Direction.RIGHT;
while(arr[i][j]==0){
arr[i][j]=num++;
switch(dir){
case RIGHT:
if((j+1<arr[0].length)&&arr[i][j+1]==0)
j++;
else{
i++;
dir=Direction.DOWN;
}
break;
case DOWN:
if((i+1<arr.length)&&arr[i+1][j]==0)
i++;
else{
j--;
dir=Direction.LEFT;
}
break;
case LEFT:
if((j-1>=0)&&arr[i][j-1]==0)
j--;
else{
i--;
dir=Direction.UP;
}
break;
case UP:
if((i-1>=0)&&arr[i-1][j]==0)
i--;
else{
j++;
dir=Direction.RIGHT;
}
break;
}
}
print(arr);
}else
System.out.println(1);
}
public static void print(int[][] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++)
System.out.print(arr[i][j]+" ");
System.out.println();
}
}
public enum Direction{
RIGHT,DOWN,LEFT,UP
}
public static void main(String []args){
Test t=new Test();
t.spire();
}
}