0

次のようにリストする必要があります。

a = ["1a","2a","3a","4a","5a","6a","7a","8a","9a","10a","11a","12a","13a","14a"] 
b = ["1b","2b","3b","4b","5b","6b","7b","8b","9b","10b","11b","12b","13b","14b"]

そして、私が望むのは、それらを組み合わせて、 a の要素とbの対応する要素の間に少なくともn要素の違いがあるようにすることです。

例として、私のnが 10 で、"3a" が 3 番目の位置にあり、"3b" が 5 番目の位置にある場合、これらの対応する要素間の距離は 2 しかないため、これは解決策ではありません。

私は、ブルート フォース メソッドを使用して、必要な目的のためにこれを既に解決しています。2 つの配列の和集合をシャッフルし、制約が満たされているかどうかを確認します。そうでない場合は、もう一度シャッフルします...言うまでもなく、14要素の配列の場合、最小距離が10の解を得るために5〜10秒の計算が必要になることがあります。探しているので、これをより最適化された方法で解決する方法に興味があります。

私は現在 Python を使用していますが、任意の言語 (または疑似コード) のコードは大歓迎です。

編集: この問題のコンテキストは、約 100 人の参加者が参加することが期待されるアンケートのようなものです。したがって、私は必ずしもすべてのソリューションに関心があるわけではなく、最初の 100 のようなものです。

ありがとう。

4

3 に答える 3

1

特定のシナリオでは、ランダム化されたアプローチを使用できますが、すでに試したほどランダムではありません。このようなもの：

  1. 両方のリストのアイテムをランダムに並べ替えることから始めます
  2. 他のアイテムのコピーを作成し、 2 つのアイテムをランダムに交換することにより、新しい順列を作成します。
  3. 順列の品質を測定します。たとえば、関連するアイテムの各ペアの距離の合計、またはそのような距離の最小値です。
  4. 新しい順列の品質が元の順列の品質よりも優れている場合は、新しい順列を保持し、そうでない場合は新しい順列を破棄して元の順列を続行します
  5. 各距離が少なくとも10になるまで、または何回か繰り返しても品質が改善されなくなるまで、2.から繰り返します。

（あなたのアプローチのように）各反復でリスト全体をシャッフルすることとの違いは、満足のいく解決策が見つかるまで、各反復で順列が良くなるということです。

このアルゴリズムを実行するたびに、結果はわずかに異なるため、100 の異なるソリューションに対して 100 回実行できます。もちろん、このアルゴリズムは解決策を見つけることを保証するものではありません(そのようなすべての解決策ははるかに少ない) が、失敗した場合に再起動できるように十分に高速である必要があります。

Python では、これは次のようになります (少し単純化されていますが、まだ機能しています)。

def shuffle(A, B):
    # original positions, i.e. types of questions
    kind = dict([(item, i) for i, item in list(enumerate(A)) + list(enumerate(B))])

    # get positions of elements of kinds, and return sum of their distances
    def quality(perm):
        pos = dict([(kind[item], i) for i, item in enumerate(perm)])
        return sum(abs(pos[kind[item]] - i) for i, item in enumerate(perm))

    # initial permutation and quality
    current = A + B
    random.shuffle(current)
    best = quality(current)

    # improve upon initial permutation by randomly swapping items
    for g in range(1000):
        i = random.randint(0, len(current)-1)
        j = random.randint(0, len(current)-1)
        copy = current[:]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality(copy)
        if q > best:
            current, best = copy, q

    return current

の出力例print shuffle(a, b):

['14b', '2a', '13b', '3a', '9b', '4a', '6a', '1a', '8a', '5b', '12b', '11a', ' 10b'、'7b'、'4b'、'11b'、'5a'、'7a'、'8b'、'12a'、'13a'、'14a'、'1b'、'2b'、'3b' 、「6b」、「10a」、「9a」]

于 2013-06-25T17:29:08.137 に答える
0

Python に .NET の Lists および LINQ に相当するものがある場合は、次のコードを直接変換できる場合があります。最大 100 個のリストを非常に迅速に生成します。「デバッグ」を押して実行すると、1 秒もかからずにウィンドウがポップアップして結果が表示されます。

' VS2012
Option Infer On

Module Module1

    Dim minDistance As Integer = 10
    Dim rand As New Random ' a random number generator

    Function OkToAppend(current As List(Of Integer), x As Integer) As Boolean
        ' see if the previous minDistance values contain the number x
        Return Not (current.Skip(current.Count - minDistance).Take(minDistance).Contains(x))
    End Function

    Function GenerateList() As List(Of String)
        ' We don't need to start with strings: integers will make it faster.
        ' The "a" and "b" suffixes can be sprinkled on at random once the
        ' list is created.
        Dim numbersToUse() As Integer = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

        Dim pool As New List(Of Integer)
        ' we need all the numbers twice
        pool.AddRange(numbersToUse)
        pool.AddRange(numbersToUse)

        Dim newList As New List(Of Integer)

        Dim pos As Integer

        For i = 0 To pool.Count - 1
            ' limit the effort it puts in
            Dim sanity As Integer = pool.Count * 10

            Do
                pos = rand.Next(0, pool.Count)
                sanity -= 1
            Loop Until OkToAppend(newList, pool(pos)) OrElse sanity = 0

            If sanity > 0 Then ' it worked
                ' append the value to the list
                newList.Add(pool(pos))
                ' remove the value which has been used
                pool.RemoveAt(pos)
            Else ' give up on this arrangement
                Return Nothing
            End If

        Next

        ' Create the final list with "a" and "b" stuck on each value.
        Dim stringList As New List(Of String)
        Dim usedA(numbersToUse.Length) As Boolean
        Dim usedB(numbersToUse.Length) As Boolean

        For i = 0 To newList.Count - 1
            Dim z = newList(i)
            Dim suffix As String = ""

            If usedA(z) Then
                suffix = "b"
            ElseIf usedB(z) Then
                suffix = "a"
            End If

            ' rand.Next(2) generates an integer in the range [0,2)
            If suffix.Length = 0 Then suffix = If(rand.Next(2) = 1, "a", "b")

            If suffix = "a" Then
                usedA(z) = True
            Else
                usedB(z) = True
            End If

            stringList.Add(z.ToString & suffix)
        Next

        Return stringList

    End Function

    Sub Main()
        Dim arrangements As New List(Of List(Of String))
        For i = 1 To 100
            Dim thisArrangement = GenerateList()
            If thisArrangement IsNot Nothing Then
                arrangements.Add(thisArrangement)
            End If
        Next

        'TODO: remove duplicate entries and generate more to make it up to
        ' the required quantity.
        For Each a In arrangements
            ' outputs the elements of a with ", " as a separator
            Console.WriteLine(String.Join(", ", a))
        Next

        ' wait for user to press enter
        Console.ReadLine()

    End Sub

End Module
于 2013-06-25T18:56:44.603 に答える
0

あなたの質問から私が理解しているように、配列のインデックス (つまり、純粋な整数) のみに依存することですべての順序付けを実行できるため、各要素を分析する代わりに (有効な) 範囲を作成するために問題を減らすことができます。

a <= total_items-n ごとに、有効な b = if(a + n == total_items){total_items} else{[a + n, total_items]}

例えば：

n = 10; 合計アイテム = 15;

a = 1 の場合 -> 有効な b = [11, 15]

a = 2 の場合 -> 有効な b = [12, 15]

など

これは 4 回実行されます。b に対する a の前方および後方と、a に対する b の同じです。

このようにして、反復回数を最小の式に減らし、出力として、1 対 1 のバインディングではなく、各位置の「ソリューション」のセットを取得します (これが現在持っているものです。ではない？）。

于 2013-06-25T17:28:20.147 に答える