有一个兑换商品的业务问题，关于排列组合的编程问题想问一下大伙，有对头的小伙伴们？

[DavidNineRoc]

有一个兑换功能，表格大概如下：

users(用户表)
+-----------------------+
| id     name           |
| 1      admin          |
| 2      guest          |
| 3      home           |
+-----------------------+

goods(商品表)
+-----------------------+
| id     name           |
| 1      A              |
| 2      B              |
| 3      C              |
| 4      D              |
+-----------------------+

buy_history(用户购买记录表)
+-------------------------+
| user_id good_id  number |
| 1        1         10   |
| 1        2         20   |
| 1        3         19   |
| 2        4         47   |
+-----------------------+

explains(兑换规则表)
+-------------------------------------------------+
| combination  combination_number good_id  number |
| 1              10                 2        1    |
| 1,2            15                 1        2    |
| 1,2,3          30                 3        2    |
| 2,3            20                 2        2    |
+-------------------------------------------------+

这个表的记录意思是： explains.combination是需要组合的 id，简单的说明。 如第一条记录是指商品 1 买够了 10 个数量，可以兑换商品 2 数量 1 个. 第二条记录是指，买够了商品 1 或者 2 加起来总共有 15 个的可以兑换商品 1 数量 2 个 第三条记录是指，买够了商品 1 或者 2 或者 3 总共有 30 个的可以兑换商品 3 数量 2 个。

业务是这样的: 用户每次买了商品之后，在购买记录表记录下数量，然后管理员可以添加任意种组合到兑换规则表，需要组合的商品有可能是一个或者多个商品的 id(explains.ombination)，但是可以兑换的商品（ good_id ）只会只一个。

---

现在我想的是先用编程语言计算好所有排列组合， 如上面的用户购买记录表，可以得出用户 1 的组合是：

# 用户 1 的购买记录
| 1        1         10   |
| 1        2         20   |
| 1        3         19   |
# 得出所有的集合，key 是 combination 组合，value 是数量
| 1 => 11 | 2 => 20 | 3 => 19 | 1,2 => 30 | 1,3 => 29 | 2,3 => 39 | 1,2,3 => 49|

组合的个数是这样的： Cn1 + Cn2 + Cn3 + Cn4 + Cn(n-1) 然后再用所有的组合key，whereIn一下explains.combination组合，再遍历每一条记录中需要的combination_number，然后得出符合条件的。 有做过这方面的朋友可以指教一下？

[DavidNineRoc]

别沉

[xiaoxinshiwo]

自己把自己绕死。举例：
把 | 1,2,3 30 3 2 | 拆开成三条不就行了吗？

[xiaoxinshiwo]

@xiaoxinshiwo #2 错了，忽略

[akira]

用户数和商品数 一定是比 兑换数要少几个量级的，是我设计的话，会从兑换表入手来处理

[gaius]

用户自选多好

[knightlhs]

@DavidNineRoc
是否需要考虑 兑换后的购买总量可以扣减 扣减后总和不满足后面条件的情况
比如 2,3 30 3 2 这个使用后 1,2 10 1 1 这个条件中由于 2 的总数在上条规则中使用过 而不满足当前规则的情况

[DavidNineRoc]

@akira 可以说一下你的思路？
@gaius 肯定不行的，不满足条件你查出来选，用户会怪异，肯定是查用户满足条件的。
@knightlhs 需要，现在只是查询用户能兑换的，让他选择。当用户兑换之后会减去用户购买记录表里的数量。

[ccpp132]

先计算所以的组合是不现实的。学习一下指数时间复杂度的含义？

[DavidNineRoc]

@ccpp132 那么依你的想法呢。

[akira]

@DavidNineRoc 先获取所有奖励组合，这个组合应该是不会频繁变更，并且可以缓存的。
然后逐个组合判断 用户所购买的 商品 是否满足要求。