2

ある間隔内で定義される 3 種類の数値範囲が あり
ます 。 1、3、7など)

それらを結合/交差させ（異なるタイプの2からNまで）、最適化された結果を得る必要があります。明らかに、上記の交差は上記のタイプのいずれかの結果を返し、それらを結合すると上記のタイプの 1 から M の範囲になります。
例 1:
1 番目の範囲は 5 から 11 までの連続した範囲として定義され、2 番目の範囲は 2 から 18 までのステップ 2 (したがって 8 ステップ) の周期的なシーケンスとして定義されます。
Intersection は、ステップ 2 で 6 から 10 までの周期的シーケンスを
返します。Union は、ステップ 2 で 2 から 4 までの周期的シーケンス、ステップ 2 で 5 から 11 までの連続範囲、およびステップ 2 で 12 から 18 までの周期的シーケンスの 3 つの結果を返します。
例 2:
1 番目の範囲はステップ 2 の周期シーケンス 0 から 10 として定義され、2 番目はステップ 2 の 1 から 7 の周期シーケンス (したがって 3 ステップ) として定義されます。
交差は交差しないため、null を返します。
Union は 2 つの結果を返します: ステップ 1 を含む 1 から 8 までの周期的なシーケンス (注: 最適化された結果) と正確な値 10
.
ここのようなもののためのライブラリがあることを願っています。アドバイスをお願いします (C#.NET で使用します)。
ありがとう！

更新
「ライブラリをどのように使用すると思いますか」への回答。上記の 3 つのタイプはすべて、プログラミング言語で次のように簡単に定義できます
。10 進数の終了。ここで、Start は範囲の始まりで、End は終わり
です。10 進ステップ; int カウント; ここで、Start はシーケンスの開始、Step はインクリメント、Count はステップ カウント
3 です。正確な数値のセット: { decimal[] Values; ここで、Values はいくつかの 10 進数の配列です。

上記の任意のタイプの任意の 2 つの範囲の交差を作成すると、そのタイプのいずれかの結果が確実に得られます。また、「正確なセット」は、正確な「連続」のセットになります。また、「exact」は正確も返します。同じタイプの交差は、入力タイプの結果を返します。
2 つの範囲の結合はもう少し複雑ですが、上記の型で定義された 2 ～ 3 つの範囲も返します。
交差/結合関数を使用すると、常に2からNの範囲で実行でき、入力タイプの用語で結果を取得できます。

4

2 に答える 2

2

まず、以前の他の回答に従ってください:これには標準ライブラリがあるとは思いません:それは非常に特殊なケースのように見えます。

第二に、問題/要件が十分に明確に述べられていません。問題の紹介に従い、3 つの異なるタイプを「セット」、「周期的」、「連続」と呼びます。

{1,4,5,6} と {4,5,6,8} の 2 つのセットを考えます。それらの交点は {4,5,6} です。その説明がケースに適合するため「周期的」とラベル付けする必要がありますか、それともセットの交差であるため「セット」とラベル付けする必要がありますか?

このことから、より一般的には、内容が定期的であるとすぐに「セット」ラベルを「定期的」に変更する必要がありますか? 結局のところ、「定期」は「セット」の特殊なケースです。

同様に、「周期的な」{4,6,8} と集合 {10,15,16} の結合を考えてみましょう。結果を周期的な {4,6,8,10} に周期的な {15,16} を加えたものとして定義する必要がありますか、それともすべての値を含む 1 つのセットとして、またはさらに別の種類として定義する必要がありますか?

また、退化したケースについてはどうですか: {3} は「セット」、「周期的」、または「連続」でさえありますか? "continuous"{1-4} と "set"{4,7,8} の共通部分は何ですか? 連続{1-4}と連続{4-7}の交点？

など: 結合および/または交差からの結果がどのようにラベル付け/記述されなければならないかを明確にする必要があります。セット、場合によっては定期刊行物)、またはむしろ常に一連の定期刊行物、または...

第 3 に、上記の質問に対処したと仮定すると、次のガイドラインに従って実装に取り​​組むことができると思います。

  • 「連続」と「セット」の 2 つの「タイプ」のみを考慮してください。「周期的」は「セット」の特別な形式にすぎず、必要に応じていつでも「セット」を「周期的」とラベル付けすることができます。

  • 共通の基本クラスを定義し、ユニオン、交差、および必要に応じて適切な派生 (オーバーロード) メソッドを使用して、結果として (baseType の) リストなどを生成します。

ケースバイケースの実装は、基本的に非常に単純です - 私の最初の質問が答えられていると仮定します。最初の問題がやや「難しい」と思われる場合はいつでも、それは問題と仕様がまだ十分に定義されていないためです。

于 2012-10-04T14:43:48.997 に答える
0

それはすべて非常にカスタムに聞こえます-したがって、それらすべてをペグから外したライブラリを見つけることはないと思います-しかし、それほど難しいことは何もありません.

始めます。最初の例では問題なく動作しますが、「ステップ 2 で 2 から 4 までの周期的シーケンス、ステップ 2 で 5 から 11 までの連続範囲、およびステップ 2 で 12 から 18 までの周期的シーケンス」Range.ConstructAppropriateを返すには、メソッドが特に複雑になる必要があります。例 1 の 2 つの集合の和集合から生じる集合。{ 5, 6, 7, 8, 9, 10, 11, 2, 4, 12, 14, 16, 18 }

また、（すべてのコードを配線する手間をかけた後）コメントから、非整数の要件があることに注意してください。これは物事を複雑にします。このパターンを適用する創造的な方法を思い付くことができると思います。

class Program
{
    static void Main(string[] args)
    {
        // Example 1:
        // 1st range is defined as continous range from 5 to 11 and 2nd is periodical sequence from 2 to 18 with step 2 (thus, 8 steps).
        // Intersection will return a periodic sequence from 6 to 10 with step 2.example 1

        ContinuousRange ex1_r1 = new ContinuousRange(5, 11);
        PeriodicRange ex1_r2 = new PeriodicRange(2, 2, 8);

        IEnumerable<int> ex1_intersection = ex1_r1.Values.Intersect(ex1_r2.Values);
        IList<Range> ex1_intersection_results = Range.ConstructAppropriate(ex1_intersection);
    }
}

abstract class Range
{
    public abstract IEnumerable<int> Values { get; }

    public static IList<Range> ConstructAppropriate(IEnumerable<int> values)
    {
        var results = new List<Range>();

        results.Add(ContinuousRange.ConstructFrom(values));
        results.Add(PeriodicRange.ConstructFrom(values));

        if (!results.Any(r => r != null))
            results.Add(Points.ConstructFrom(values));

        return results.Where(r => r != null).ToList();
    }
}

class ContinuousRange : Range
{
    int start, endInclusive;

    public ContinuousRange(int start, int endInclusive)
    {
        this.start = start;
        this.endInclusive = endInclusive;
    }

    public override IEnumerable<int> Values
    {
        get
        {
            return Enumerable.Range(start, endInclusive - start + 1);
        }
    }

    internal static ContinuousRange ConstructFrom(IEnumerable<int> values)
    {
        int[] sorted = values.ToArray();
        if (sorted.Length <= 1)
            return null;

        for (int i = 1; i < sorted.Length; i++)
        {
            if (sorted[i] - sorted[i - 1] != 1)
                return null;
        }

        return new ContinuousRange(sorted.First(), sorted.Last());
    }
}

class PeriodicRange : Range
{
    int start, step, count;

    public PeriodicRange(int start, int step, int count)
    {
        this.start = start;
        this.step = step;
        this.count = count;
    }

    public override IEnumerable<int> Values
    {
        get
        {
            var nums = new List<int>();
            int i = start;
            int cur = 0;

            while (cur <= count)
            {
                nums.Add(i);
                i += step;
                cur++;
            }

            return nums;
        }
    }

    internal static Range ConstructFrom(IEnumerable<int> values)
    {
        // check the difference is the same between all values

        if (values.Count() < 2)
            return null;

        var sorted = values.OrderBy(a => a).ToArray();

        int step = sorted[1] - sorted[0];

        for (int i = 2; i < sorted.Length; i++)
        {
            if (step != sorted[i] - sorted[i - 1])
                return null;
        }

        return new PeriodicRange(sorted[0], step, sorted.Length - 1);
    }
}

class Points : Range
{
    int[] nums;

    public Points(params int[] nums)
    {
        this.nums = nums;
    }

    public override IEnumerable<int> Values
    {
        get { return nums; }
    }

    internal static Range ConstructFrom(IEnumerable<int> values)
    {
        return new Points(values.ToArray());
    }
}
于 2012-10-04T13:24:55.227 に答える