1到2n这2n个数平均分成两份 abs(ai-bi)=k 求个数

本文主要是介绍1到2n这2n个数平均分成两份 abs(ai-bi)=k 求个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入是两个正整数n和k，把从1到2n这2n个数平均分成两份(每份n个数)，每份分别排序，排序完成后的数组假设叫a和b，要求abs(ai-bi)>=k, (相同位置的数差的绝对值不少于k),输出有多少种分法。

Backtrack is straighforward, welcome other better solutions:

from itertools import combinationsclass Solution:def cal_ways(self, n, k):def dfs(toset, sta, y):nonlocal k,nl = len(sta)if (l == n and y == n):return 1elif (l == y and l+k <= n):return 2*dfs(k+toset, sta+[i+toset for i in range(k)], y)elif (l == y and l+k > n):return 0else:ret = 0if (l < n):ret += dfs(toset+1, sta+[toset], y)if ((abs(sta[y]-toset) >= k)):ret += dfs(toset+1, sta, y+1)return retres = dfs(1+k, [i+1 for i in range(k)], 0)return resdef cal_direct(self, n, k):total = [i+1 for i in range(n*2)]cnt,xycnt = 0,0for comb in combinations([i+1 for i in range(n*2)], n):a = list(comb)b = sorted(list(set(total).difference(set(a))))if (all(abs(a[i]-b[i]) >= k for i in range(n))):cnt += 1return cnt >> 1s = Solution()for i in range(1,10):for j in range(1,i+1):res1 = s.cal_ways(i, j)res2 = s.cal_direct(i, j)if (res1 != res2):print("n={0} k={1} res1={2} res2={3}".format(i,j,res1,res2))
print("Finished!!!")

Dependencies are the major difficulty. E.g., n=7, k=3, after arrangement of [1,2,3],the arrangement of 4,5,6 has 3 scenarios:

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