汇的子集输出(排列组合)集合的子集输出(排列组合)

by admin on 2018年9月19日

题目:从n个整数中觅有y只整数,输出所有结成。

问题:从n个整数中寻找有y只整数,输出所有结成。

例如:1,2,3 这个集找来2独整数,组合产生:1,2; 1,3; 2,3 共三种植情景

譬如说:1,2,3 这个集找有2只整数,组合出:1,2; 1,3; 2,3 共三种植情形

 

 

实现:

实现:

思路:
可以想像成彩票选球,例如双色球,从33独球被选取6个圆球出来,第一糟发生33种植可能,第二赖发出32栽或….,举个简单例子,从1,2,3这集中选出2只数,如图所示

思路:
可以想象变为彩票选球,例如双色球,从33个圆球中摘6单球出来,第一坏发出33种可能,第二差闹32种植可能….,举个简易例子,从1,2,3之集中选出2独数,如图所示

图片 1

图片 2

具体的java实现代码如下:

实际的java实现代码如下:

package com.hdwang;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by hdwang on 2016/12/26.
 */
public class Combine {
    /**
     * 集合(球)
     */
    int[] ball;

    /**
     * 排列子集
     */
    List<String> subColListPL = new ArrayList<String>();

    /**
     * 组合子集
     */
    List<String> subColListCH = new ArrayList<String>();

    /**
     * 子集大小(元素个数)
     */
    int subSize = 1;

    Combine(int size,int subSize){
        //初始化集合
        this.ball = new int[size];
        for(int i=0;i<size;i++){
            this.ball[i] = i+1;
//            this.ball[i] = i;
        }
        //定义子集大小
        this.subSize = subSize;
    }

    /**
     * 产生子集
     */
    public void generateSubCol(){

        //选择第一个球
        for(int i=0;i<ball.length;i++){
            int[] subBall = new int[this.subSize]; //由n个数组暂存子集元素
            subBall[0] = ball[i]; //子集第一个球的选择

            forFunc(subBall,1); //设置子集第二个球
        }

        //打印排列
        System.out.println("打印排列集合:");
        for(int i=0;i< this.subColListPL.size();i++){
            System.out.print(subColListPL.get(i));
            System.out.print("; ");
        }
        //找出组合
        for(int i=0;i<this.subColListPL.size();i++){
            String subColStr = subColListPL.get(i);
            subColStr = sortSubCol(subColStr); //对子集排序一下(组合按照从小大小的规则输出)
            if(!this.subColListCH.contains(subColStr)){ //去重
                this.subColListCH.add(subColStr);
            }
        }
        //打印组合
        System.out.println("\n打印组合集合:");
        for(int i=0;i< this.subColListCH.size();i++){
            System.out.print(subColListCH.get(i));
            System.out.print("; ");
        }
    }

    /**
     * 循环方法
     * @param subBall 子集
     * @param index 子集将设置值的位置
     */
    private void forFunc(int[] subBall,int index){
        if(index == this.subSize){ //某一种排列产生
            String subBallStr = this.join(subBall);
            this.subColListPL.add(subBallStr);
            return; //退出递归
        }

        int remainBallLen = ball.length-index; //剩余可选球个数
        int[] availableBall = new int[remainBallLen];
        int j=0;
        for(int i=0;i<ball.length;i++){
            int  preLen = index; //subBall前多少个球已选
            if(!contains(subBall,ball[i],preLen)){ //不在子集中的球
                availableBall[j] = ball[i];
                j++;
            }
        }


        for(int i=0;i<availableBall.length;i++){
            subBall[index] = availableBall[i]; //指定位置赋值(选第index+1个球)


            forFunc(subBall, index + 1); //递归调用
            subBall[index] = 0; //恢复值(可略)
        }
    }


    /**
     *  数组前几个元素是否等于某值
     * @param array 数组
     * @param value 值
     * @param preLen 前几个元素
     * @return 是否存在
     */
    private boolean contains(int[] array,int value,int preLen){
        boolean c = false;
        if(array == null){
            return false;
        }
        for(int i=0;i<preLen;i++){
            if(array[i] == value){
                c = true;
                break;
            }
        }
        return c;
    }

    /**
     * 数组转字符串
     * @param array 数组
     * @return 字符串(逗号分隔)
     */
    public String join(int[] array){
        String str ="";
        for(int i=0;i<array.length;i++){
            str += array[i]+",";
        }
        return str.substring(0,str.length()-1);
    }

    /**
     * 子集排序一下(例如: 1,3,2 -> 1,2,3 )
     * @param subColStr 子集字符串
     * @return 排序后的字符串
     */
    private String sortSubCol(String subColStr) {
        String[] subcolArray = subColStr.split(",");
        int[] subcol = new int[subcolArray.length];
        for(int i=0;i<subcolArray.length;i++){
            subcol[i] = Integer.parseInt(subcolArray[i]);
        }

        sort(subcol);
        return join(subcol);
    }

    /**
     * 冒泡排序
     * @param array 整型数组
     */
    public void sort(int[] array){
        for(int i=0;i< array.length-1;i++){ //比多少次
            for(int j= i+1;j<array.length;j++){ //每次循环,将最小数置前
                if(array[i]>array[j]){ //小数冒泡
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

}
package com.hdwang;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by hdwang on 2016/12/26.
 */
public class Combine {
    /**
     * 集合(球)
     */
    int[] ball;

    /**
     * 排列子集
     */
    List<String> subColListPL = new ArrayList<String>();

    /**
     * 组合子集
     */
    List<String> subColListCH = new ArrayList<String>();

    /**
     * 子集大小(元素个数)
     */
    int subSize = 1;

    Combine(int size,int subSize){
        //初始化集合
        this.ball = new int[size];
        for(int i=0;i<size;i++){
            this.ball[i] = i+1;
//            this.ball[i] = i;
        }
        //定义子集大小
        this.subSize = subSize;
    }

    /**
     * 产生子集
     */
    public void generateSubCol(){

        //选择第一个球
        for(int i=0;i<ball.length;i++){
            int[] subBall = new int[this.subSize]; //由n个数组暂存子集元素
            subBall[0] = ball[i]; //子集第一个球的选择

            forFunc(subBall,1); //设置子集第二个球
        }

        //打印排列
        System.out.println("打印排列集合:");
        for(int i=0;i< this.subColListPL.size();i++){
            System.out.print(subColListPL.get(i));
            System.out.print("; ");
        }
        //找出组合
        for(int i=0;i<this.subColListPL.size();i++){
            String subColStr = subColListPL.get(i);
            subColStr = sortSubCol(subColStr); //对子集排序一下(组合按照从小大小的规则输出)
            if(!this.subColListCH.contains(subColStr)){ //去重
                this.subColListCH.add(subColStr);
            }
        }
        //打印组合
        System.out.println("\n打印组合集合:");
        for(int i=0;i< this.subColListCH.size();i++){
            System.out.print(subColListCH.get(i));
            System.out.print("; ");
        }
    }

    /**
     * 循环方法
     * @param subBall 子集
     * @param index 子集将设置值的位置
     */
    private void forFunc(int[] subBall,int index){
        if(index == this.subSize){ //某一种排列产生
            String subBallStr = this.join(subBall);
            this.subColListPL.add(subBallStr);
            return; //退出递归
        }

        int remainBallLen = ball.length-index; //剩余可选球个数
        int[] availableBall = new int[remainBallLen];
        int j=0;
        for(int i=0;i<ball.length;i++){
            int  preLen = index; //subBall前多少个球已选
            if(!contains(subBall,ball[i],preLen)){ //不在子集中的球
                availableBall[j] = ball[i];
                j++;
            }
        }


        for(int i=0;i<availableBall.length;i++){
            subBall[index] = availableBall[i]; //指定位置赋值(选第index+1个球)


            forFunc(subBall, index + 1); //递归调用
            subBall[index] = 0; //恢复值(可略)
        }
    }


    /**
     *  数组前几个元素是否等于某值
     * @param array 数组
     * @param value 值
     * @param preLen 前几个元素
     * @return 是否存在
     */
    private boolean contains(int[] array,int value,int preLen){
        boolean c = false;
        if(array == null){
            return false;
        }
        for(int i=0;i<preLen;i++){
            if(array[i] == value){
                c = true;
                break;
            }
        }
        return c;
    }

    /**
     * 数组转字符串
     * @param array 数组
     * @return 字符串(逗号分隔)
     */
    public String join(int[] array){
        String str ="";
        for(int i=0;i<array.length;i++){
            str += array[i]+",";
        }
        return str.substring(0,str.length()-1);
    }

    /**
     * 子集排序一下(例如: 1,3,2 -> 1,2,3 )
     * @param subColStr 子集字符串
     * @return 排序后的字符串
     */
    private String sortSubCol(String subColStr) {
        String[] subcolArray = subColStr.split(",");
        int[] subcol = new int[subcolArray.length];
        for(int i=0;i<subcolArray.length;i++){
            subcol[i] = Integer.parseInt(subcolArray[i]);
        }

        sort(subcol);
        return join(subcol);
    }

    /**
     * 冒泡排序
     * @param array 整型数组
     */
    public void sort(int[] array){
        for(int i=0;i< array.length-1;i++){ //比多少次
            for(int j= i+1;j<array.length;j++){ //每次循环,将最小数置前
                if(array[i]>array[j]){ //小数冒泡
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

}

调用示例:

调用示例:

package com.hdwang;

/**
 * Created by admin on 2016/12/26.
 * 组合测试
 */
public class CombineTest {

    public static void main(String[] args){
        Combine combine = new Combine(3,2);
        combine.generateSubCol();


//        int[] array = {3,1};
//        combine.sort(array);
//        System.out.println(combine.join(array));
    }
}
package com.hdwang;

/**
 * Created by admin on 2016/12/26.
 * 组合测试
 */
public class CombineTest {

    public static void main(String[] args){
        Combine combine = new Combine(3,2);
        combine.generateSubCol();


//        int[] array = {3,1};
//        combine.sort(array);
//        System.out.println(combine.join(array));
    }
}

出口结果:

输出结果:

打印排列集合:
1,2; 1,3; 2,1; 2,3; 3,1; 3,2;
打印组合集合:
1,2; 1,3; 2,3;

打印排列集合:
1,2; 1,3; 2,1; 2,3; 3,1; 3,2;
打印组合集合:
1,2; 1,3; 2,3;

 

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图