回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我有一份钥匙清单:</p>
<pre class="lang-py prettyprint-override"><code>['A', 'B', 'C']
</code></pre>
<p>对于每个键,都有一个属性列表:</p>
<pre class="lang-py prettyprint-override"><code>{
'A': [2,3],
'B': [1,2],
'C': [4]
}
</code></pre>
<p>我希望对标签列表进行排序,以便相邻标签共享尽可能多的属性</p>
<p>在上面的示例中<code>A</code>和<code>B</code>共享关系<code>2</code>,因此它们应该彼此相邻-而<code>C</code>与它们不共享任何内容,因此它可以去任何地方</p>
<p>因此,本例的可能顺序如下:</p>
<pre class="lang-py prettyprint-override"><code>["A","B","C"] # acceptable
["A","C","B"] # NOT acceptable
["B","A","C"] # acceptable
["B","C","A"] # NOT acceptable
["C","A","B"] # acceptable
["C","B","A"] # acceptable
</code></pre>
<h2>水桶</h2>
<p>事实上,我更希望通过将它们放入“桶”来表示:</p>
<pre class="lang-py prettyprint-override"><code>[["A", "B"], ["C"]] # this can represent all four possible orders above.
</code></pre>
<p>但是,如果标签属于两个不同的存储桶,则会出现问题:</p>
<pre class="lang-py prettyprint-override"><code>{
'A': [2,3],
'B': [1,2],
'C': [1,4]
}
</code></pre>
<p>我将如何陈述这一点</p>
<p>我可以这样说:</p>
<pre class="lang-py prettyprint-override"><code>[["A", "B"], ["C", "B"]]
</code></pre>
<p>但我需要另一个处理步骤来翻转桶列表
在最后陈述中:</p>
<pre class="lang-py prettyprint-override"><code>["A", "B", "C"]
</code></pre>
<p>除此之外,还可能存在递归嵌套的bucket:</p>
<pre class="lang-py prettyprint-override"><code>[[["A","B"], ["C"]], ["D"]]
</code></pre>
<p>然后这些可能重叠:</p>
<pre class="lang-py prettyprint-override"><code>[[["A","B"], ["C"]], ["A","D"]]
</code></pre>
<h2>品质</h2>
<p>“接近度”,即解的质量定义为相邻关系的交集之和(质量越高越好):</p>
<pre class="lang-py prettyprint-override"><code>def measurequality(result,mapping):
lastKey = None
quality = 0
for key in result:
if lastKey is None:
lastKey = key
continue
quality += len(set(mapping[key]).intersection(mapping[lastKey]))
lastKey = key
return quality
# Example determining that the solution ['A', 'B', 'C'] has quality 1:
#measurequality(['A', 'B', 'C'],
# {
# 'A': [2,3],
# 'B': [1,2],
# 'C': [4]
# })
</code></pre>
<h2>暴力强迫</h2>
<p>暴力强制并不构成解决方案(实际上,列表包含数千个元素——不过,如果有人得到了比<code>O(n²)</code>更好的暴力强制方法……)</p>
<p><em>但是</em>,使用暴力强制创建额外的测试用例是可能的:</p>
<ul>
<li>生成<code>L</code>个<code>n</code>项的列表<code>['A','B','C',...]</code></li>
<li>为每个项目生成一个关系字典<code>R</code>(在<code>0</code>和<code>n</code>之间最多有<code>n</code>个随机数就足够了)</李>
<li>生成所有可能的<code>L</code>排列,并将它们与<code>R</code>一起馈送到<code>measurequality()</code>中,并保留那些具有最大返回值的排列(可能不是唯一的)</李>
</ul>
<p>用于创建随机测试用例以测试实现的代码:</p>
<pre class="lang-py prettyprint-override"><code>import string
import random
def randomtestcase(n):
keys=list(string.ascii_uppercase[0:n])
minq = 0
maxq = 0
while minq == maxq:
items={}
for key in keys:
items[key] = random.sample(range(1,10),int(random.random()*10))
minq = n*n
minl = list(keys)
maxq = 0
maxl = list(keys)
for _ in range(0, 1000): # TODO: explicitly construct all possible permutations of keys.
random.shuffle(keys)
q = measurequality(keys,items)
if q < minq:
minq = q
minl = list(keys)
if maxq < q:
maxq = q
maxl = list(keys)
return ( items, minl, maxq )
( items, keys, quality ) = randomtestcase(5)
sortedkeys = dosomething( keys, items )
actualquality = measurequality( sortedkeys, items )
if actualquality < quality:
print('Suboptimal: quality {0} < {1}'.format(actualquality,quality))
</code></pre>
<h2>企图</h2>
<p>许多“解决方案”中不起作用的一个(非常糟糕,这一个没有初始元素的选择/在结果列表的前置和追加之间的选择,我在其他列表中有):</p>
<pre class="lang-py prettyprint-override"><code>def dosomething(keys,items):
result = []
todo = list(keys)
result.append(todo.pop())
while any(todo):
lastItems = set(items[result[-1]])
bestScore = None
bestKey = None
for key in todo:
score = set(items[key]).intersection(lastItems)
if bestScore is None or bestScore < score:
bestScore = score
bestKey = key
todo.remove(bestKey)
result.append(bestKey)
return result
</code></pre>
<h2>例子</h2>
<p>(<em>还可以查看上文<strong>暴力强制部分中的示例生成器。</em>)</p>
<p>测试代码尝试以下示例:</p>
<pre class="lang-py prettyprint-override"><code>def test(description,acceptable,keys,arguments):
actual = dosomething(keys,arguments)
if "".join(actual) in acceptable:
return 0
print("\n[{0}] {1}".format("".join(keys),description))
print("Expected: {0}\nBut was: {1}".format(acceptable,actual))
print("Quality of result: {0}".format(measurequality(actual,arguments)))
print("Quality of expected: {0}".format([measurequality(a,arguments) for a in acceptable]))
return 1
print("EXAMPLES")
failures = 0
# Need to try each possible ordering of letters to ensure that the order of keys
# wasn't accidentially already a valid ordering.
for keys in [
["A","B","C"],
["A","C","B"],
["B","A","C"],
["B","C","A"],
["C","A","B"],
["C","B","A"]
]:
failures += test(
"1. A and B both have 2, C doesn't, so C can go first or last but not in between.",
["ABC", "BAC", "CAB", "CBA"],
keys,
{
"A": [2,3],
"B": [1,2],
"C": [4]
})
failures += test(
"2. They all have 2, so they can show up in any order.",
["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"],
keys,
{
"A": [2,3],
"B": [1,2],
"C": [2]
})
failures += test(
"3. A and B share 2, B and C share 1, so B must be in the middle.",
["ABC", "CBA"],
keys,
{
"A": [2,3],
"B": [1,2],
"C": [1]
})
failures += test(
"4. Each shares something with each other, creating a cycle, so they can show up in any order.",
["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"],
keys,
{
"A": [2,3],
"B": [1,2],
"C": [1,3]
})
if 0 < failures:
print("{0} FAILURES".format(failures))
</code></pre>
<h2>优先权</h2>
<p>正如有人问的那样:用于关系的数字没有优先顺序。存在一个优先顺序,但它是一个偏序,而不是一个数字。我只是没有提到它,因为它让问题变得更难</p>
<p>举个例子:</p>
<pre class="lang-py prettyprint-override"><code>{
'A': [2,3],
'B': [1,2],
'C': [4]
}
</code></pre>
<p>可替换为以下内容(使用字母而不是数字,并添加优先级信息):</p>
<pre class="lang-py prettyprint-override"><code>{
'A': [('Q',7),('R',5)],
'B': [('P',6),('Q',6)],
'C': [('S',5)]
}
</code></pre>
<p>注意</p>
<ul>
<li>优先级仅在列表中有意义,而在列表之间没有意义</李>
<li>两个列表之间共享关系的优先级可能不同</李>
<li>在一个列表中,可能会多次出现相同的优先级</李>
</ul>