7

私はあなたのために頭の体操を手に入れました-それは思ったほど単純ではないので、読んで問題を解決してみてください。宿題かどうか尋ねる前に-そうではありません！これを解決するためのエレガントな方法があるかどうかを確認したいだけです。問題は次のとおりです。

X人の友人が映画館に行きたいと思っており、利用可能な最高のグループに着席したいと思っています。最良の場合は全員が一緒に座っていることであり、最悪の場合は全員が一人で座っていることです。より少ないグループがより多くのグループよりも優先されます。バランスの取れたグループが優先されます（4+2よりも3+3の方が優先されます）。一人で座ることは最も好ましくありません。

入力は映画館に行く人の数であり、出力は以下を含む整数配列の配列である必要があります。

  • 順序付けられた組み合わせ（最も好ましいのは最初です）
  • 各グループの人数

以下は、映画館に行く人々の数のいくつかの例と、これらの人々が着席できる好ましい組み合わせのリストです。

  • 1人：1
  • 2人：2、1 + 1
  • 3人：3、2 + 1、1 + 1 + 1
  • 4人：4、2 + 2、3 + 1、2 + 1 + 1、1 + 1 + 1 + 1
  • 5人：5、3 + 2、4 + 1、2 + 2 + 1、3 + 1 + 1、2 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1
  • 6人：6、3 + 3、4 + 2、2 + 2 + 2、5 + 1、3 + 2 + 1、2 + 2 + 1 + 1、2 + 1 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1 + 1

7人以上の例が組み合わせて爆発しますが、今ではポイントがわかると思います。

質問は：この問題を解決するアルゴリズムはどのように見えるか？私が選んだ言語はC＃なので、C＃で答えていただければ素晴らしいと思います。

4

3 に答える 3

4

再帰的に行う必要があると思いますが、同じグループを何度も分割し続けないようにする必要があります。これにより、指数関数的な実行時間が得られます。私のソリューションでは、私は O(n*n) を持っているようです (あなたは私のためにそれを確認することができます;) 、以下の結果を見てください。もう1つは、あなたが言及した望ましさの機能です。そのような関数がどのように見えるかはわかりませんが、代わりに 2 つのパーティションを比較できます。たとえば、パーティション 1 + 1 + 2 + 4 は 1 + 2 + 2 + 3 ほど望ましくありません。一般的なルールは、「別のパーティションよりもグループ化された人数が同じである場合、そのパーティションは望ましくない」ということです。理にかなっており、より多くの人が一緒に座るほど良い. 私の解決策は、2 つの可能なグループ化を比較するためにこのアプローチを採用し、あなたが達成したい結果を得ることができます。

        var sut = new BrainTeaser();

        for (int n = 1; n <= 6; n++) {
            StringBuilder sb = new StringBuilder();
            sb.AppendFormat("{0} person{1}: ", n, n > 1 ? "s" : "");

            var array = sut.Solve(n).Select(x => x.ToString()).ToArray();
            sb.AppendLine(string.Join(", ", array));

            Console.WriteLine(sb.ToString());
        }

1人：1

2人：2、1+1

3人：3、1+2、1+1+1

4人：4、2+2、1+3、1+1+2、1+1+1+1

5人：5、2+3、1+4、1+2+2、1+1+3、1+1+1+2、1+1+1+1+1

6人：6、3+3、2+4、2+2+2、1+5、1+2+3、1+1+4、1+1+2+2、1+1+1+3 、1+1+1+1+2、1+1+1+1+1+1

パフォーマンスは O(n*n) のようです:

var sut = new BrainTeaser();

 for (int n = 1; n <= 40; n++) {
   Stopwatch watch = new Stopwatch();
   watch.Start();
   var count = sut.Solve(n).Count();
   watch.Stop();
   Console.WriteLine("Problem solved for {0} friends in {1} ms. Number of solutions {2}", n, watch.ElapsedMilliseconds, count);
}

Problem solved for 1 friends in 17 ms. Number of solutions 1
Problem solved for 2 friends in 49 ms. Number of solutions 2
Problem solved for 3 friends in 2 ms. Number of solutions 3
Problem solved for 4 friends in 1 ms. Number of solutions 5
Problem solved for 5 friends in 0 ms. Number of solutions 7
Problem solved for 6 friends in 2 ms. Number of solutions 11
Problem solved for 7 friends in 0 ms. Number of solutions 15
Problem solved for 8 friends in 0 ms. Number of solutions 22
Problem solved for 9 friends in 1 ms. Number of solutions 30
Problem solved for 10 friends in 1 ms. Number of solutions 42
Problem solved for 11 friends in 4 ms. Number of solutions 56
Problem solved for 12 friends in 4 ms. Number of solutions 77
Problem solved for 13 friends in 7 ms. Number of solutions 101
Problem solved for 14 friends in 9 ms. Number of solutions 135
Problem solved for 15 friends in 15 ms. Number of solutions 176
Problem solved for 16 friends in 21 ms. Number of solutions 231
Problem solved for 17 friends in 30 ms. Number of solutions 297
Problem solved for 18 friends in 43 ms. Number of solutions 385
Problem solved for 19 friends in 61 ms. Number of solutions 490
Problem solved for 20 friends in 85 ms. Number of solutions 627
Problem solved for 21 friends in 117 ms. Number of solutions 792
Problem solved for 22 friends in 164 ms. Number of solutions 1002
Problem solved for 23 friends in 219 ms. Number of solutions 1255
Problem solved for 24 friends in 300 ms. Number of solutions 1575
Problem solved for 25 friends in 386 ms. Number of solutions 1958
Problem solved for 26 friends in 519 ms. Number of solutions 2436
Problem solved for 27 friends in 677 ms. Number of solutions 3010
Problem solved for 28 friends in 895 ms. Number of solutions 3718
Problem solved for 29 friends in 1168 ms. Number of solutions 4565
Problem solved for 30 friends in 1545 ms. Number of solutions 5604
Problem solved for 31 friends in 2025 ms. Number of solutions 6842
Problem solved for 32 friends in 2577 ms. Number of solutions 8349
Problem solved for 33 friends in 3227 ms. Number of solutions 10143
Problem solved for 34 friends in 4137 ms. Number of solutions 12310
Problem solved for 35 friends in 5300 ms. Number of solutions 14883
Problem solved for 36 friends in 6429 ms. Number of solutions 17977
Problem solved for 37 friends in 8190 ms. Number of solutions 21637
Problem solved for 38 friends in 10162 ms. Number of solutions 26015
Problem solved for 39 friends in 12643 ms. Number of solutions 31185

ソリューションに含まれる 3 つのクラスを投稿します。

public class BrainTeaser {
    /// <summary>
    /// The possible groupings are returned in order of the 'most' desirable first. Equivalent groupings are not returned (e.g. 2 + 1 vs. 1 + 2). Only one representant
    /// of each grouping is returned (ordered ascending. e.g. 1 + 1 + 2 + 4 + 5)
    /// </summary>
    /// <param name="numberOfFriends"></param>
    /// <returns></returns>
    public IEnumerable<PossibleGrouping> Solve(int numberOfFriends) {
        if (numberOfFriends == 1) {
            yield return new PossibleGrouping(1);
            yield break;
        }
        HashSet<PossibleGrouping> possibleGroupings = new HashSet<PossibleGrouping>(new PossibleGroupingComparer());
        foreach (var grouping in Solve(numberOfFriends - 1)) {
            // for each group we create 'n+1' new groups 
            // 1 + 1 + 2 + 3 + 4 
            // Becomes
            //      (1+1) + 1 + 2 + 3 + 4  we can add a friend to the first group
            //      1 + (1+1) + 2 + 3 + 4  we can add a friend to the second group
            //      1 + 1 + (2+1) + 3 + 4  we can add a friend to the third group
            //      1 + 1 + 2 + (3+1) + 4  we can add a friend to the forth group
            //      1 + 1 + 2 + 3 + (4+1) we can add a friend to the fifth group
            //      (1 + 1 + 2 + 3 + 4) + 1  friend has to sit alone

            AddAllPartitions(grouping, possibleGroupings);
        }
        foreach (var possibleGrouping in possibleGroupings.OrderByDescending(x => x)) {
            yield return possibleGrouping;
        }
    }

    private void AddAllPartitions(PossibleGrouping grouping, HashSet<PossibleGrouping> possibleGroupings) {
        for (int i = 0; i < grouping.FriendsInGroup.Length; i++) {
            int[] newFriendsInGroup = (int[]) grouping.FriendsInGroup.Clone();
            newFriendsInGroup[i] = newFriendsInGroup[i] + 1;
            possibleGroupings.Add(new PossibleGrouping(newFriendsInGroup));
        }
        var friendsInGroupWithOneAtTheEnd = grouping.FriendsInGroup.Concat(new[] {1}).ToArray();
        possibleGroupings.Add(new PossibleGrouping(friendsInGroupWithOneAtTheEnd));
    }
}

/// <summary>
/// A possible grouping of friends. E.g.
/// 1 + 1 + 2 + 2 + 4 (10 friends). The array is sorted by the least friends in an group.
/// </summary>
public class PossibleGrouping : IComparable<PossibleGrouping> {
    private readonly int[] friendsInGroup;

    public int[] FriendsInGroup {
        get { return friendsInGroup; }
    }

    private readonly int sum;

    public PossibleGrouping(params int[] friendsInGroup) {
        this.friendsInGroup = friendsInGroup.OrderBy(x => x).ToArray();
        sum = friendsInGroup.Sum();
    }

    public int Sum {
        get { return sum; }
    }

    /// <summary>
    /// determine which group is more desirable. Example:
    /// Consider g1: 1 + 2 + 3 + 4 vs g2: 1 + 1 + 2 + 2 + 4  
    /// Group each sequence by the number of occurrences:
    /// 
    /// group   | g1   | g2
    /// --------|-------------
    /// 1       | 1    | 2
    /// ----------------------
    /// 2       | 1    | 2
    /// ----------------------
    /// 3       | 1    | 0
    /// ----------------------
    /// 4       | 1    | 1
    /// ----------------------
    /// 
    /// Sequence 'g1' should score 'higher' because it has 'less' 'ones' (least desirable) elements. 
    /// 
    /// If both sequence would have same number of 'ones', we'd compare the 'twos'.
    /// 
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public int CompareTo(PossibleGrouping other) {
        var thisGroup = (from n in friendsInGroup group n by n).ToDictionary(x => x.Key,
                                                                             x => x.Count());

        var otherGroup = (from n in other.friendsInGroup group n by n).ToDictionary(x => x.Key,
                                                                                    x => x.Count());

        return WhichGroupIsBetter(thisGroup, otherGroup);
    }

    private int WhichGroupIsBetter(IDictionary<int, int> thisGroup, IDictionary<int, int> otherGroup) {
        int maxNumberOfFriendsInAGroups = Math.Max(thisGroup.Keys.Max(), otherGroup.Keys.Max());

        for (int numberOfFriendsInGroup = 1;
             numberOfFriendsInGroup <= maxNumberOfFriendsInAGroups;
             numberOfFriendsInGroup++) {
            // zero means that the current grouping does not contain a such group with 'numberOfFriendsInGroup'
            // in the example above, e.g. group '3'
            int thisNumberOfGroups = thisGroup.ContainsKey(numberOfFriendsInGroup)
                                         ? thisGroup[numberOfFriendsInGroup]
                                         : 0;
            int otherNumberOfGroups = otherGroup.ContainsKey(numberOfFriendsInGroup)
                                          ? otherGroup[numberOfFriendsInGroup]
                                          : 0;

            int compare = thisNumberOfGroups.CompareTo(otherNumberOfGroups);

            if (compare != 0) {
                // positive score means that the other group has more occurrences. e.g. 'this' group might have 2 groups with each 2 friends,
                // but the other solution might have 3 groups with each 2 friends. It's obvious that (because both solutions must sum up to the same value)
                // this 'solution' must contain a grouping with more than 3 friends which is more desirable.
                return -compare;
            }
        }
        // they must be 'equal' in this case.
        return 0;
    }

    public override string ToString() {
        return string.Join("+", friendsInGroup.Select(x => x.ToString()).ToArray());
    }
}

public class PossibleGroupingComparer : EqualityComparer<PossibleGrouping> {
    public override bool Equals(PossibleGrouping x, PossibleGrouping y) {
        return x.FriendsInGroup.SequenceEqual(y.FriendsInGroup);
    }

    /// <summary>
    /// may not be the best hashcode function. for alternatives look here: http://burtleburtle.net/bob/hash/doobs.html
    /// I got this code from here: http://stackoverflow.com/questions/3404715/c-sharp-hashcode-for-array-of-ints
    /// </summary>
    /// <param name="obj"></param>
    /// <returns></returns>
    public override int GetHashCode(PossibleGrouping obj) {
        var array = obj.FriendsInGroup;

        int hc = obj.FriendsInGroup.Length;
        for (int i = 0; i < array.Length; ++i) {
            hc = unchecked(hc*314159 + array[i]);
        }
        return hc;
    }
}

今すぐ解決策に：

頭の体操クラスは再帰を行います。このクラスのトリックの 1 つは、ハッシュセットでカスタム比較子 ( PossibleGroupingComparer) を使用することです。これにより、新しいグループ (例: 1+1+2 対 2+1+1) を計算するときに、それらが同じものとして扱われることが保証されます (セットには、同等のグループごとに 1 つの代表のみが含まれます)。これにより、指数関数的な実行時間が O(n^2) に短縮されます。

次のトリックは、PossibleGroupingsクラスが IComparable を実装しているため、結果の順序付けが可能であることです。Compare() メソッドの実装は、上記の考え方を使用しています。このメソッドには基本的にこのソリューションの塩が含まれており、別の方法でグループ化する場合は、このメソッドのみを変更する必要があります。

コードを理解していただければ幸いです。そうでない場合はお知らせください。読みやすくしようとしましたが、パフォーマンスはあまり気にしませんでした。たとえば、グループを呼び出し元に返す前にのみグループを並べ替えることができます。再帰内の並べ替えはあまり役に立ちません。

ただし、1 つのコメント: 典型的なシナリオは、映画館が「既に」多くの座席を予約しており、「任意の」パーティションを許可しない場合です。ここでは、すべてのパーティションを取得し、現在のシネマで使用できるかどうかを 1 つずつ確認する必要があります。これは機能しますが、不要な CPU コストがかかります。代わりに、入力を使用して再帰の数を減らし、全体の実行時間を改善できます。多分誰かがこれに対する解決策を投稿したいでしょう;）

于 2012-04-05T10:51:34.697 に答える
2

私があなたを正しく理解していると仮定すると、これを再帰的に行うことができます。

  • 1 人の場合、グループ化は1.
  • 人物の場合n、グルーピングはすべて、人物と残りの人物のグルーピング、1人物と残りのn-1人物のグルーピングなどです。2n-2

可能なグループ化のリストを取得したら、必要な基準に基づいて「望ましさ」で並べ替えることができます。

于 2012-04-04T19:06:51.213 に答える
1

これは、最速の既知アルゴリズムを使用してすべてのパーティションを列挙する関数です

    public static List<List<int>> EnumerateAll(int n)
    {
        /* Fastest known algorithim for enumerating partitons
         * (not counting the re-ordering that I added)
         * Based on the Python code from http://homepages.ed.ac.uk/jkellehe/partitions.php
         */
        List<List<int>> lst = new List<List<int>>();
        int[] aa = new int[n + 1];
        List<int> a = new List<int>(aa.ToList<int>());
        List<int> tmp;
        int k = 1;

        a[0] = 0;
        int y = n - 1;

        while (k != 0)
        {
            int x = a[k - 1] + 1;
            k -= 1;
            while (2 * x <= y)
            {
                a[k] = x;
                y -= x;
                k += 1;
            }
            int l = k + 1;
            while (x <= y)
            {
                a[k] = x;
                a[l] = y;

                // copy just the part that we want
                tmp = (new List<int>(a.GetRange(0, k + 2)));

                // insert at the beginning to return partions in the expected order
                lst.Insert(0, tmp);
                x += 1;
                y -= 1;
            }
            a[k] = x + y;
            y = x + y - 1;

            // copy just the part that we want
            tmp = (new List<int>(a.GetRange(0, k + 1)));

            // insert at the beginning to return partions in the expected order
            lst.Insert(0, tmp);
        }

        return lst;
    }

そして、あなたの好みに応じて（上記の）返されたパーティションのリストを並べ替える関数があります：

    /// <summary>
    /// ReOrders a list of partitons placing those with the smallest groups last
    ///   NOTE: this routine assumes that each partitoning lists the smallest 
    ///   integers *first*.
    /// </summary>
    public static IList<List<int>> ReOrderPartitions(IList<List<int>> source)
    {
        // the count is used in several places
        long totalCount= source.Count;
        long k = 0;     // counter to keep the keys unique

        SortedList<long, List<int>> srt = new SortedList<long, List<int>>(source.Count);

        foreach (List<int> prt in source)
        {
            srt.Add(-(prt[0] * totalCount) + k, prt);
            k++;
        }

        return srt.Values;
    }

最後に、コントロール イベントから呼び出してこれらの関数を呼び出し、結果を ListBox に表示できるメソッドを次に示します。(注: 「Partitions」は、上記の関数を含むクラスです)

    private void ListPreferredPartitons(int n, ListBox listOut)
    {
        IList<List<int>> pts = Partitions.EnumerateAll(n);
        pts = Partitions.ReOrderPartitions(pts);

        listOut.Items.Clear();

        foreach (List<int> prt in pts)
        {
            // reverse the list, so that the largest integers will now be first.
            prt.Reverse();
            string lin = "";
            foreach (int k in prt)
            {
                if (lin.Length > 0) lin += ", ";
                lin += k.ToString();
            }
            listOut.Items.Add(lin);
        }
    }
于 2012-04-05T15:28:15.157 に答える