如何生成最小的相邻和不同数字序列？

Question

例如，我想要一个函数，给定 + 或 - 符号（升序和降序），使不超过 8 位数字的最小序列不同且相邻

输入示例：

my_function("---")
output: 4321

my_function("-+-")
output: 2143

my_function("+-+-")
output: 13254

我正在尝试：


def my_function(sequence):
    result=[]
    values = list(range(1, len(sequence)+2))
    print(values)
    for i in sequence:
        if(i == "-"):
            print(values[-1])
            result.append(values[-1])
            values.pop(-1)
        else:
            result.append(values[0])
            values.pop(0)

    result.append(values[0])
    return result
    
print(my_function("+-+-"))

Answer 1

此方法基于 brute-force 方法：计算从 1 到 len('+-+-') + 1 的所有数字排列，然后检查每个连续对是否满足 increasing/decreasing 条件：

(1, 3, 2, 5, 4) --> [('+', 1, 3), ('-', 3, 2), ('+', 2, 5), ('-', 5, 4)] --> [True, True, True, True]。它 returns 第一场比赛。

import itertools as it

def my_func(seq):
    for perm in it.permutations(range(1, len(seq)+2)):

        if all(a<b if rel == '+' else a>b for rel, a, b, in zip(seq, perm, perm[1:])):
            return ''.join(map(str, perm))

seqs = ["---", "-+-", "+-+-", "++", '-+-']

print([(seq, my_func(seq)) for seq in seqs])

输出

[('---', '4321'), ('-+-', '2143'), ('+-+-', '13254'), ('++', '123'), ('-+-', '2143')]

备注：使用递归方法会“更干净”

编辑要记住问题的组合性质，您可以使用 itertools.product 输出所有可能的顺序

n = 4 # amount of order operations
seqs = it.product('+-', repeat=n)

print([(''.join(seq), my_func(seq)) for seq in seqs])

Answer 2

解决方案：

def my_function(sequence):
    result = []
    sequence = list(sequence)
    values = list(range(1, len(sequence)+2))
    contDescending, contAscending= 0, 0
    last=""
    for i, ordem in enumerate(sequence):
        last = ordem if i == 0 else last
        if(ordem!=last):
            last=ordem
            if(contAscending>0):
                for j in range(contAscending):
                    result.append(values[0])
                    values.pop(0)
            if(contDescending>0):
                for k in range(contDescending):
                    result.append(values[contDescending-k])
                    values.pop(contDescending-k)
            contDescending, contAscending= 0, 0

        contDescending+=1 if ordem == "-" else contDescending
        contAscending+=1 if ordem == "+" else contAscending 

        if(i == len(sequence)-1):
            if(contAscending>0):
                for j in range(contAscending):
                    result.append(values[0])
                    values.pop(0)

            if(contDescending>0):
                for k in range(contDescending):
                    result.append(values[contDescending-k])
                    values.pop(contDescending-k)
            
            contDescending, contAscending= 0, 0
            result.append(values[0])
    return int("".join(map(str, result)))

如何生成最小的相邻和不同数字序列？

How can I generate the smallest sequence of adjacent and distinct numbers?

python

numbers

graph

list

python-3.x