大小 k 与条件的所有组合

大佬教程收集整理的这篇文章主要介绍了大小 k 与条件的所有组合，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

如何解决大小 k 与条件的所有组合？

开发过程中遇到大小 k 与条件的所有组合的问题如何解决？下面主要结合日常开发的经验，给出你关于大小 k 与条件的所有组合的解决方法建议，希望对你解决大小 k 与条件的所有组合有所启发或帮助；

我被这个问题困扰了好几天：

我试图在 C++ 上获得整数向量的组合，但有条件，这将允许我计算更大的组合。例如：

• 让向量 N = [1,2,3,4]（所以这里 n = 4）和 k = 2
• 和地图形式的条件（int - > vector）：
• 1 -> [3]
• 2 - > [4]
• 3 -> [1,4]
• 4 -> [2,3]

这里的意思是1不能和3组合，2不能和4组合，3不能和1和4组合...

对于 k = 2，我们得到：

• [1,2]
• [1,4]
• [2,3]

目前，我正在计算所有组合，然后过滤它们，但是对于较大的 n 和较大的 k，这需要很多时间。所以我们的想法是避免无用的计算组合。

感谢您的帮助！

编辑：

为了更清楚：

对于 n = 4 和 k = 2，我们有以下组合：

• 1 2
• 1 3
• 1 4
• 2 3
• 2 4
• 3 4

并且是条件映射（类型 map ）： //number：不能关联的整数向量

• 1 : [3]
• 2 : [4]
• 3 : [1,4]
• 4 : [2,3]

但是如果我们考虑到条件：

• 1 2 -> 这个组合是有效的，因为 1 不能与 3 相关联，这意味着它可以与 2,3 相关联，而 2 不能与 4 相关联，即它可以与 1,3 相关联。
• 1 3 -> 此组合无效，因为 1 不能与 3 相关联。
• 1 4 -> 这个组合是有效的，因为 1 可以与除 3 之外的所有内容相关联。
• 2 3 -> 这个组合是有效的，因为 2 可以与除 4 以外的任何东西相关联。
• 2 4 -> 此组合无效，因为 2 不能与 4（反之亦然）。
• 3 4 -> 这个组合是无效的，因为 3 不能和 1 也不能和 4。

因此：

• [1,3]

也可以在每个整数之间添加条件。对于 k = 3，例如：

• 1 2 4 是无效组合，因为虽然 1 可以与 2 和 4 相关联，但 2 和 4 不能相关联。
• 1 2 3 也是如此，因为 1 和 3 不能关联在一起。

（此外，这里没有 k = 3 的有效组合）。

我试过了（我使用python是因为它对我来说更简单，但解决方案必须在C++中可行，伪代码就足够了）：

def ini_comb(arr,ex,n,k):
    
    data = [0]*k
    comb(arr,data,n - 1,k)

def comb(arr,start,end,index,k):
                        
    if (index == k):

        for j in range(k):
            print(data[j],end = " ")

        print()
        return

    i = start

    while(i <= end and end - i + 1 >= k - indeX):

        test = 1
        data[index] = arr[i]

        for k in data:
            if k:
                for j in ex[k-1]:
                    if j in data:
                        test = 0
                        break
                if not test:
                    break
        
        if test:
            comb(arr,i + 1,index + 1,k)
        i += 1


arr = [1,4]
n = len(arr)
k = 2
ex = [[3],[4],[1,4],[3,2]]
ini_comb(arr,k)

这里我用一个简单的递归来遍历所有的组合，当其中一个不满足ex列表的条件时，我就不用它做递归了。但它不起作用，因为我只得到：[1 2]。

解决方案：

解决办法： 这是为那些需要它的人提供的解决方案（在 python 中）！正如@Jarod42 所建议的，我使用回溯算法，并在进行递归之前检查组合的有效性：

def p(arr,eX):
    ret = [] 
    def BACk_track(start_IDx,temp,eX):
        ret.append(temp)
        for i in range(start_IDx,len(arr)):
            test = 1
            for k in temp + [arr[i]]:
                if k:
                    for j in ex[k-1]:
                        if j in temp + [arr[i]]:
                            test = 0
                            break
                    if not test:
                        break
        
            if test:
                BACk_track(i + 1,temp + [arr[i]],eX)
    BACk_track(0,[],eX)
    return ret

arr = [1,4,5,6]
n = len(arr)
ex = [[4],[5],6],[2,[4,5]]

res = p(arr,eX)
res.sort(key=len,reverse=TruE)

for i in res:
    print(i)
    print("\n")

解决方法

暂无找到可以解决该程序问题的有效方法，小编努力寻找整理中！

如果你已经找到好的解决方法，欢迎将解决方案带上本链接一起发送给小编。

小编邮箱:dio#foxmail.com (将#修改为@）

大佬总结

以上是大佬教程为你收集整理的大小 k 与条件的所有组合全部内容，希望文章能够帮你解决大小 k 与条件的所有组合所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。