代码之家 › 专栏 › 技术社区 › fean

查找所有可能的组合-java[closed]

combinations algorithm arrays java

-3

fean · 技术社区 · 11 年前

我需要找到以下方式给出的数据的组合,

jobs  #ofIntervals
----  -------------
4     1
1     2
3     2
0     3
2     3

必须根据Intervals的数量对给定的作业进行组合。输出可能的组合将影响作业的位置。若有多个作业具有相同的间隔数,则只有对这些作业位置的更改才会生成新的作业集。给定输入的可能结果应该是这样的,

combination-1: 4 1 3 0 2    // same as input

combination-2: 4 3 1 0 2    // here as job 3 and 1 have 2 #ofIntervals they make a new combination 

combination-3: 4 1 3 2 0    // here as job 2 and 0 have 3 #ofIntervals they make a new combination

combination-4: 4 3 1 2 0

有人能帮我写一个代码或建议一个算法吗。

2 回复 | 直到 11 年前

e-sushi amandanovaes 10 年前

将作业分成不同的集合,其中集合的每个成员都具有相同的“间隔数”值。
对于每个集合,生成一个集合,其中包含 permutations 那一套的。
生成一个集合,该集合包含 cartesian product 步骤2中的集合。

这个最终的集合就是您的解决方案。

BPaasch 11 年前

我喜欢mbeckish写的答案,但以下是我为实际完成这项工作而写的代码:

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

public class Test
{
    public static void main(String[] args)
    {
        List<JobsInterval> jobsIntervalList = new ArrayList<JobsInterval>();

        jobsIntervalList.add(new JobsInterval(4, 1));
        jobsIntervalList.add(new JobsInterval(1, 2));
        jobsIntervalList.add(new JobsInterval(3, 2));
        jobsIntervalList.add(new JobsInterval(0, 3));
        jobsIntervalList.add(new JobsInterval(2, 3));

        printPossibleCombinations(jobsIntervalList);
    }

    public static void printPossibleCombinations(List<JobsInterval> list)
    {
        //Assumes the list is already in interval order.
        int currentInterval = -1;
        List<List<JobsInterval>> outerList = new ArrayList<List<JobsInterval>>(list.size());
        List<JobsInterval> innerList = null;

        //Loop through the list and group them into separate lists by interval.
        for (JobsInterval ji : list)
        {
            if (ji.interval != currentInterval)
            {
                if (null != innerList)
                    outerList.add(innerList);

                currentInterval = ji.interval;
                innerList = new ArrayList<JobsInterval>(list.size());
            }

            innerList.add(ji);
        }

        if (null != innerList)
            outerList.add(innerList);

        print(0, outerList, null);
    }

    public static void permute(StringBuilder value, List<JobsInterval> list, List<String> permutations)
    {
        //Check to see if this is the last recursive call
        if (0 == list.size())
        {
            permutations.add(value.toString());
        }
        else
        {
            List<JobsInterval> subList;

            for (int i = 0; i < list.size(); i++)
            {
                subList = new ArrayList<>(list);
                subList.remove(i);
                permute(new StringBuilder(null == value ? "" : value).append(list.get(i).jobs), subList, permutations);
            }
        }
    }

    public static void print(int index, List<List<JobsInterval>> list, StringBuilder value)
    {
        //Check to see if this is the last recursive call
        if (list.size() == index)
            System.out.println(value.toString());
        else
        {
            List<JobsInterval> intervalGroup = list.get(index);
            List<String> permutations = new ArrayList<String>();

            permute(null, intervalGroup, permutations);

            for (String permutation : permutations)
                print(index+1, list, new StringBuilder(null == value ? "" : value).append(permutation));
        }
    }

    private static class JobsInterval
    {
        public int jobs;
        public int interval;

        public JobsInterval(int j, int i)
        {
            jobs = j;
            interval = i;
        }

        public String toString()
        {
            return new StringBuilder().append('{').append(jobs).append(", ").append(interval).append('}').toString();
        }
    }
}