有n（奇数偶数皆可）个人排队，排成两排，要求：右边的人要比左边的人高，第一排的人要比第二排的人高

Question

本帖最后由 OptimusMan 于 2010-12-04 14:43:28 编辑

Answer 1

这简单，
直接排一排，右边比左边高（升序）即可。（任何排序方法都可以）然后依次（从0到length-1)断取偶数序号的数字放第一排,断取奇数序号的数字放到第二排

Answer 2

如果只需要知道多少种情况，楼主可以搜下 catalan 数
如果需要输出全部结果，用回溯做这个比较不错

Answer 3

如果只是说同排右边必须比左边高，则可以这样做。
1. 依然要先排序
2. 按序号从0到length-1将每个元素分往某排，每个序号上的元素可自由选择去第一排还是去第二排，只需要遵守两个原则：
2.1 已分到第一排的个数必须不大于已分到第二排的个数
上例的特殊情况是
2.2 如果大于了，则后面所有数字必须全放第一排

Answer 4

还有就是用Java打印输出，怎么实现让元素自由选择。 谢谢

Answer 5

import java.util.*;public class Test {
static int count;
  public static void main(String[] args)
  {
  int[] num={1,2,3,4,5,7,9,6,8,10};
  Arrays.sort(num);
 sorted(num);
  }
  
public static void sorted(int[] num){
combination(num,0,0,num.length,num.length /2);
System.out.println("有"+count+"种方法");
}
public static void combination(int a[],int start,int step,int n,int m)
{
if(step==m)
{
//count++;
int [] num1=new int[a.length /2];
int [] num2=new int[a.length /2];
for(int i=0;i<m;i++)
{
num1[i]=a[i];
}
for(int i=m;i<a.length;i++)
{
num2[i-a.length /2]=a[i];
}
if(isOk(num1,num2))
{
count++;
for(int i=0;i<num1.length;i++)
System.out.print(num1[i]+" ");
System.out.print("\n");
for(int i=0;i<num2.length;i++)
System.out.print(num2[i]+" ");
System.out.print("\n\n");
} }
else
{
for(int j=start;j<n;j++)
{
int temp=a[step];
a[step]=a[j];
a[j]=temp;
combination(a,j+1,step+1,n,m);
a[j]=a[step];
a[step]=temp;
}

}

}
public static boolean isOk(int[] num1,int []num2)
{
Arrays.sort(num1);
Arrays.sort(num2);
for(int i=0;i<num1.length;i++)
{
if(num1[i]<num2[i])
return false;
}
return true;
}
}print:2 4 6 8 10 
1 3 5 7 9 2 4 6 9 10 
1 3 5 7 8 2 4 7 8 10 
1 3 5 6 9 2 4 7 9 10 
1 3 5 6 8 2 4 8 9 10 
1 3 5 6 7 2 5 6 8 10 
1 3 4 7 9 2 5 6 9 10 
1 3 4 7 8 2 5 7 8 10 
1 3 4 6 9 2 5 7 9 10 
1 3 4 6 8 2 5 8 9 10 
1 3 4 6 7 2 6 7 8 10 
1 3 4 5 9 2 6 7 9 10 
1 3 4 5 8 
.
.
.
有42种方法

Answer 6

OK，那么这样，我9楼的思想，对应的是下面的代码（排序过程略）
public class CatalanNumber {
// int[] value=new int[]{12,4,3,6,7,1,11,2,9,8,10};
static int[] value = new int[]{1,2,3,4,6,7,8,9,10,11,12}; //排序算法略
static int count = 0; public static void main(String[] args) {
List list1 = new ArrayList();  //此排要高
List list2 = new ArrayList();  //此排要小，应该先排
arrange(list1, list2, 0);
}

private static void arrange(List list1, List list2, int position){
if (position==value.length){ //得到一个排列
count++;
System.out.println("" + count + ":");
System.out.println("List 1:" + list1);
System.out.println("List 2:" + list2);
}else if (list1.size()>list2.size()){ //已经成为了特例
list1.add(value[position]);  //干脆维持特例
arrange(list1, list2, position+1);
}else{
List list1Cpy = new ArrayList(list1);
List list2Cpy = new ArrayList(list2);
list1.add(value[position]);  //可以加到一排
arrange(list1, list2, position+1);
list2Cpy.add(value[position]);  //也可以加到二排
arrange(list1Cpy, list2Cpy, position+1);
}
}}