黑马程序员技术交流社区

标题: 组合数字能力和循环 [打印本页]

作者: 林康春 时间: 2012-7-11 23:23
标题: 组合数字能力和循环
需求：有1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？都是多少：
class  Demo7
{
public static void main(String[] args)
{
//System.out.println("Hello World!");
int [] n={1,2,3,4};
int m=3;
get();
}

// 简单算法的实现
public static void get()
{
   int [] n={1,2,3,4};
   int m=3;
   int length=n.length;//数组的长度
   int number=0;//计数变量

   for (int i=0;i<length;i++ )
   {
   if (i==0)
   {
   System.out.println(n[1]+""+n[2]+""+n[3]);
   number++;
   }else if (i==1)
   {
   System.out.println(n[i-1]+""+n[2]+""+n[3]);
   number++;
   }else if (i==2)
   {
   System.out.println(n[i]+""+n[i-2]+""+n[3]);
   number++;
   }else if (i==3)
   {
   System.out.println(n[1]+""+n[2]+""+n[3-i]);
   number++;
   }

   }
   System.out.println(number);

}

}
扩展一下，要是这样的需求：
有n个不同的数字，能组成多少个互不相同且无重复数字的m位数？（n>=m）

作者: 周刚 时间: 2012-7-12 00:30
import java.util.ArrayList;

public class Cmn {

private String mString;
private int n;


public Cmn(String mString,int n){
      this.mString = mString;
      this.n = n;
}

private int getTheMax(){
      int lenth = mString.length();
      double maxvalue = 0;
      for(int i = 0;i<lenth; i ++ ){
         maxvalue = maxvalue + Math.pow(2, i);
      }
      return (int)maxvalue;
}

private int count1(String binaryStr){
      int count = 0;
      for(int i = 0;i<binaryStr.length();i ++){
         if(binaryStr.charAt(i) == '1'){
            count ++;
         }
      }
      return count;
}


private String[] getCmnIndexStr(){
      int maxvalue = getTheMax();
      ArrayList list = new ArrayList();
      for(int j = 1;j <= maxvalue;j ++){
         String binaryStr = Integer.toBinaryString(j);
         if(count1(binaryStr) == n){
            list.add(appendZero(binaryStr));
         }
      }
      return (String[])list.toArray(new String[0]);
}

private String appendZero(String str){
      int len = mString.length();
      if(str.length()==len){
         int sublen = len - str.length();
         String appendStr = "";
         for(int i = 0;i<sublen;i ++){
            appendStr = appendStr + "0";
         }
         str = appendStr + str;

      }
      return str;
}


private String getStrByIndexStr(String indexStr,String mstr){
      String result = "";
      for(int i = 0;i<indexStr.length();i ++){
         if(indexStr.charAt(i) == '1'){
            result = result + mstr.charAt(i);
         }
      }
      return result;
}

public String[] getCmnString(){
      if(n == 0){
         return new String[0];
      }else if(n == mString.length()){
         return new String[]{mString};
      }

      String[] indexStr = getCmnIndexStr();
      String[] cmnStr = new String[indexStr.length];
      for(int i = 0;i<indexStr.length;i ++){
         cmnStr[i] = getStrByIndexStr(indexStr[i],mString);
      }
      return cmnStr;
}

public static void main(String[] a){
int k=4;
      Cmn cmn = new Cmn("123456789",k);
      String[] str = cmn.getCmnString();
      for(int i = 0;i<str.length;i ++){
         char[]aa = str[i].toCharArray();
         for(int j=0;j<k;j++){
            System.out.print(aa[j]); //目前只实现Cmn的组合情况，至于排列需要在这里再作文章。
         }
         System.out.println();
      }
}

}

作者: 尹善波 时间: 2012-7-12 02:43
看到这个问题好像有回到了高中时代，那时候整天做这种题，还有点印象
大致思路是这样的，0~9十个数字为n，任意取值，但不能重复，最多也是取十个组合为m位数字，
1，x=n*(n-1)*...*(m+1)*(m) 这是所有组合的可能，
2, y=(n-1)*(n-2)*...*(m)*(m-1) 但是整数的第一位不能为零；y是所有零开头的总数
3，sum=x-y
输出部分应该用数组吧，代码部分就交给高手了

作者: 张天天 时间: 2012-7-12 07:43
首先说一下楼主要实现的功能，程序写的并不对
1、2、3、4取出3个能组成24个不同的3位数

说起来这应该是数学中的排列组合的问题，
如果是从n中取出m个数的话有多少种呢？
n！/（n-m）！ * m！种，然后再将首位为0的m位数去掉有就可以了
即
n*(n-1)*(n-2)*...*1/(n*(n-1)*(n-2)*...*(n-m)) * m*(m-1)*(m-2)*...*1,
像这样的阶乘在程序中用循环来实现就可以了

由于你给出的条件有限，只能写出个伪算法，
我也不能用程序表达出来，只有楼主自己去尝试了

作者: 韦念欣 时间: 2012-7-12 14:22
本帖最后由韦念欣于 2012-7-12 14:28 编辑

楼主的需求是：有1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？
这个问题是初等数学中的排列组合问题，确切的说是：排列问题。
大家一看到这样的问题，就会想到高中的一堆公式，没错，公式确实可以解决这些问题，但是公式很麻烦！
在这里，我使用巧妙的方法(递归)，来解决它，这样比公式好多了。
大家看我写的代码，这段代码解决了有n个不同的数字，能组成多少个互不相同且无重复数字的m位数这个问题！{:soso_e182:}

class Combination
{
public static int count = 0; // 排序结果数量
public static void main(String[] args)
{
String data = "1234"; // 待序列集(可以修改)
int n = 3; // 需要排序的n位数(可以修改）
combin(data, new char[n], 0); // 开始求解排序
System.out.println("在 "+data+" 中互不相同且无重复数字的"+n+"位数共有"+count+"个.");
}
public static void combin(String data, char[] result, int n)
{
if (n >= result.length) // 递归出口：排序完n位数
{ System.out.println(new String(result)); // 输出结果
count++;
return ;
}
for (int i=0; i<data.length(); i++) // 遍历数据
{ if (new String(result).indexOf(data.charAt(i)) == -1) // 移除重复的数据
{ result[n] = data.charAt(i); // 填入符合要求的数据
combin(data, result, n+1); // 继续n+1位数的遍历
result[n] = 0; // 清除当前填入数据，防止indexOf出错
}
}
}
}

复制代码

作者: 王双宝 时间: 2012-7-12 16:43
这个问题最核心的就是对一个数列进行全排列，如有x1、x2、x3（两两不相等）的一个数组，分别代表百位、十位、个位，则组成的数为x1*100+x2*10+x1*1。关键问题是如何得到全排列的问题。
对于n个两两不相等的数字，最其中n个进行全排列的排列总数为n!/m!。因此也能转化到全排列的问题上。下面我先给出对n个两两不相等的数字得到他的全排列：

public class Main {
public static void main(String[] args){
int[] array=new int[]{1,2,3,4};

int total=0;
while(null!=array){
System.out.print("第"+(++total)+"个排列为:");
for(int i=0;i<array.length;i++){
System.out.print(array[i]);
}
System.out.println();

array=sequence(array);
}

}

public static int[]  sequence(int[] array){
int i=-1;
int j=-1;
int index=array.length-1;
for(;index>=1;index--){
if(array[index-1]<array[index]){
i=index;

break;
}
else{
continue;
}
}
if(i==-1){

return null;
}
index=array.length-1;
for(;index>=i;index--){
if(array[i-1]<array[index]){
j=index;

break;
}
else{
continue;
}
}

int m=array[i-1];
array[i-1]=array[j];
array[j]=m;

int[] newarray=new int[array.length-i];
for(int index1=0,index2=array.length;index1<newarray.length;index1++,index2--){
newarray[index1]=array[index2-1];

}

for(int index4=i,index5=0;index4<array.length;index4++,index5++){
array[index4]=newarray[index5];
}

return array;

}
}
运行结果：
第1个排列为:1234
第2个排列为:1243
第3个排列为:1324
第4个排列为:1342
第5个排列为:1423
第6个排列为:1432
第7个排列为:2134
第8个排列为:2143
第9个排列为:2314
第10个排列为:2341
第11个排列为:2413
第12个排列为:2431
第13个排列为:3124
第14个排列为:3142
第15个排列为:3214
第16个排列为:3241
第17个排列为:3412
第18个排列为:3421
第19个排列为:4123
第20个排列为:4132
第21个排列为:4213
第22个排列为:4231
第23个排列为:4312
第24个排列为:4321

数学解释：

求(p)=p1pi-1pi…pn的下一个排列(q):
(1) 求 i=maxj pj-1pj (找最后一个正序)
(2) 求 j=maxk pi-1pk(找最后大于pi-1者)
(3) 互换pi-1与pj得
   p1…pi-2 pj pipi+1pj-1 pi-1 pj+1…pn
(4) 反排pj后面的数得到(q):
   p1…pi-2 pj pnpj+1pi-1pj-1 ….pi+1 pi

时间有限，后续问题有时间给出完整的解答。

作者: 王双宝 时间: 2012-7-12 17:32
本帖最后由王双宝于 2012-7-12 17:33 编辑

王双宝发表于 2012-7-12 16:43
这个问题最核心的就是对一个数列进行全排列，如有x1、x2、x3（两两不相等）的一个数组，分别代表百位、十位 ...

以下是完整代码，没有时间写注释了，下班了，给分哦。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Main {



      public static void main(String[] args){


            List<Integer> list=getList(3,1,0,2,3);

            for(Integer a : list){
                     System.out.println(a.intValue());
            }
      }






      /**
      *
      * @param array 传入的数字数组
      * @param m  从array中选中m个
      * @return
      */
      public static List<Integer> getList(int m, int ...array){
            Arrays.sort(array);
            Set<String> set=new HashSet<String>();

            while(null!=array){

                     set.add(arrayToString(array).substring(0,3));

                     array=sequence(array);

            }

            List<Integer> list=new ArrayList<Integer>();
            Iterator<String> it=set.iterator();
            while(it.hasNext()){
                     String str=it.next();
                     Integer integer=Integer.parseInt(str);
                     int min=(int) Math.pow(10,m-1);

                     if(integer>=min){
                              list.add(integer);
                     }
            }
            return list;





      }




      public static int[]  sequence(int[] array){
            int i=-1;
            int j=-1;
            int index=array.length-1;
            for(;index>=1;index--){
                     if(array[index-1]<array[index]){
                              i=index;

                              break;
                     }
                     else{
                              continue;
                     }
            }
            if(i==-1){

                     return null;
            }
            index=array.length-1;
            for(;index>=i;index--){
                     if(array[i-1]<array[index]){
                              j=index;

                              break;
                     }
                     else{
                              continue;
                     }
            }


            int m=array[i-1];
            array[i-1]=array[j];
            array[j]=m;


            int[] newarray=new int[array.length-i];
            for(int index1=0,index2=array.length;index1<newarray.length;index1++,index2--){
                     newarray[index1]=array[index2-1];

            }


            for(int index4=i,index5=0;index4<array.length;index4++,index5++){
                     array[index4]=newarray[index5];
            }


            return array;
      }


      public static String arrayToString(int[] array){
            String str="";
            for(int i=0;i<array.length;i++){
                     str+=array;
            }

            return str;

      }
}

运行结果:

203
132
210
302
301
213
123
230
201
312
310
320
321
231
120
103
102
130

作者: 林康春 时间: 2012-7-12 23:52
高手啊，辛苦了，各位
慢慢研究先

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2