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 的距离。

我已经通过蛮力方法解决了我想要的目的：打乱两个数组的并集，看看是否满足约束；如果不是，请再次随机播放，依此类推...不用说，对于 14 个元素的数组，有时需要 5 到 10 秒的计算才能产生最小距离为 10 的解决方案。尽管这对我来说还可以寻找，我很好奇如何以更优化的方式解决这个问题。

我目前正在使用 Python，但任何语言（或伪代码）的代码都非常受欢迎。

编辑：这个问题的背景有点像问卷，预计大约有 100 名参与者参加。因此，我不一定对所有解决方案感兴趣，而是对前 100 个感兴趣。

谢谢。

4

3 回答 3

1

对于您的特定场景，您可以使用随机方法——尽管不像您已经尝试过的那样随机。像这样的东西：

  1. 从两个列表中项目的随机排列开始
  2. 通过创建另一个的副本并随机交换两个项目来创建新的排列
  3. 测量排列的质量，例如，每对相关项目的距离之和，或此类距离的最小值
  4. 如果新排列的质量优于原排列，则保留新排列，否则丢弃新排列，继续原排列
  5. 从 2 开始重复，直到每个距离至少为10或直到质量在多次迭代中没有提高

在每次迭代中对整个列表进行改组（如您的方法）的区别在于，在每次迭代中，排列只能变得更好，直到找到令人满意的解决方案。

每次运行这个算法，结果都会略有不同，所以你可以运行 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

正如我从您的问题中了解到的那样，可以通过完全依赖数组的索引（即纯整数）来执行所有排序，因此可以将问题简化为创建（有效）范围而不是分析每个元素。

对于每个 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]

， ETC。

这将执行 4 次：a 相对于 b 的向前和向后，b 相对于 a 的相同。

通过这种方式，您可以将迭代次数减少到其最小表达式，并作为输出获得每个位置的一组“解决方案”，而不是一对一的绑定（这就是您现在所拥有的，不是吗？）。

于 2013-06-25T17:28:20.147 回答
0

如果 Python 中有 .NET 的 Lists 和 LINQ 的等价物，那么您可以直接转换以下代码。它非常快地生成多达 100 个列表：我按下“调试”来运行它，然后在不到一秒的时间内弹出一个带有结果的窗口。

' 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 回答