-3

次の方法で与えられたデータの組み合わせを見つける必要があります。

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

#ofIntervals に基づいて、指定されたジョブの組み合わせセットを作成する必要があります。出力可能な組み合わせは、ジョブの位置に影響します。同じ #ofIntervals を持つ複数のジョブがある場合、それらのジョブの位置を変更するだけで、新しいジョブ セットが作成されます。指定された入力の可能な結果は次のようになります。

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

誰でもコードを書いたり、そのためのアルゴリズムを提案したりできますか?

4

2 に答える 2

3
  1. ジョブを個別のセットに分けます。セットの各メンバーは同じ「間隔の数」の値を持ちます。
  2. セットごとに、そのセットのすべての順列を保持するコレクションを生成します。
  3. ステップ 2 のコレクションのデカルト積を保持するコレクションを生成します。

この最終的なコレクションがソリューションです。

于 2013-04-05T12:45:57.457 に答える
1

私は 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();
        }
    }
}
于 2013-04-05T13:41:24.100 に答える