将数组分成子数组，使得每个子数组不包含重复元素。

Question

我有一个包含32个数字的数组[1,2,3,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,9,10,10,11,12,13,13,14,14,15,16,17,17]

我想把这个数组分成8个大小为4的子数组，以便没有子数组具有重复元素。

我可以用多少种方式做到这一点？生成所有排列和单个随机排列的最优解是什么。子数组的顺序不重要。每个子数组内部元素的顺序也不重要。

对于我的原始问题，我不需要生成所有排列。我只需要在每次运行程序时生成一个随机排列。

我的方法是使用Fisher–Yates算法随机洗牌数组，并继续重新洗牌，直到我得到8个没有重复元素的子数组。当然这不是最好的方法。

作为解决方案的一部分，我会打乱数组并从这个打乱的数组中开始逐个添加元素到子数组中。如果任何子数组已经有了一个数字，那么我就跳过来自我的打乱数组的元素，直到我到达子数组中不存在的数字。这种方法在某些情况下失败。

我尝试的伪代码

let shuffledArray = shuffle(originalArray);
let subArrays = [];
for (let i = 0; i < 8; i++) {
    subArrays[i] = [];
    for (let j = 0; j < 32; j++) {
        if (!subArrays[i].contains(shuffledArray[j]) && !shuffledArray[j].used) {
            subArrays[i].push(shuffledArray[j])
            shuffledArray[j].used = true;
        }
        if (subArrays[i].length == 4) {
            break;
        }
    }
}

 if subArrays has any sub array such that it has duplicate elements then repeat above steps
 else we have generated a random permutation

如您所见，当重复的数字都在末尾时，上述方法会失败，因此我将一遍又一遍地重复所有步骤直到得到结果。

我正在使用JavaScript，但只要能转换成JavaScript，任何语言的答案都可以。

如果有人能为N个元素和K个组提供通用解决方案，那就太好了。

这是我在SO上的第一个问题。随意编辑/建议改进。

- Faizan

---

@MarkMeyer 这是可能的3种组合：[1,2,3,4][4,5,6,7][4,5,6,7][4,5,7,8][5,7,9,10][5,10,11,12][13,14,15,17][13,14,16,17] 和[1,2,13,14][4,5,16,17][4,5,6,7][4,5,7,8][5,7,9,10][5,10,11,12][13,14,15,17][3,4,6,7] 和[17,2,13,4][4,5,6,7][4,5,6,7][4,5,7,8][5,7,9,10][5,10,11,12][13,14,15,17][3,14,16,1]。 - Faizan

Answer 1

你可以使用位运算来解决这个问题。首先生成所有17位数字，其中恰好有4个位设置为1。这些数字将以某种方式表示一组可能的元素，即如果数字的第i位被设置，则i+1是该组的一部分。

现在，从这些生成的数字中，你的任务就是重复选择8个数字，满足每个元素的频率约束条件，这可以很容易地完成。

如果我找到其他方法，我会回来告诉你。

编辑：或者，您可以按以下方式递归使用：从8个数字开始，所有数字最初都设置为0，在这些数字中，将(a[i]-1)th位设置为1，而这个位在另一个数字中设置为0，并且该数字中设置的总位数小于4。

当你达到递归的叶子节点时，你将有8个数字，表示如上所述的位掩码。你可以使用它们进行分区。

你可以通过最初创建100组8个数字并从递归中返回来使用这种方法。一旦使用了所有这些100个数字，您可以再次运行此递归，以创建比前一步形成的组数多一倍的组数，以此类推。

#include<bits/stdc++.h>

using namespace std;

int num=0;
vector<vector<int> > sets;

void recur(int* arr, vector<int>& masks, int i) {
    if(num == 0)
        return;
    if(i==32){
        vector<int> newSet;
        for(int j=0; j<8; j++)
            newSet.push_back(masks[j]);
        sort(newSet.begin(), newSet.end());
        int flag=0;
        for(int j=0; j<sets.size(); j++){
            flag=1;
            for(int k=0; k<8; k++)
                flag = flag && (newSet[k] == sets[j][k]);
            if(flag) break;
        }
        if(!flag){
            sets.push_back(newSet);
            num--;
        }
        return;
    }
    for(int ii=0; ii<8; ii++) {
        if(__builtin_popcount(masks[ii]) < 4 && (masks[ii] & (1 << (arr[i]-1))) == 0){
            masks[ii] = masks[ii] ^ (1<<(arr[i] - 1));          
            recur(arr, masks, i+1);
            masks[ii] = masks[ii] ^ (1<<(arr[i] - 1));
        }
    }
}

int main() {
    num = 100;
    int num1 = num;
    vector<int> masks;
    for(int i=0; i<8; i++)
        masks.push_back(0);
    int arr[] = {1,2,3,15,16,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,9,10,10,11,12,13,13,14,14,17,17};
    recur(arr, masks, 0);
    for(int j=0; j<num1; j++){
        for(int i=0; i<8; i++){
            //ith group
            printf("%d group : ",i);
            for(int k=0; k<17; k++){
                if(sets[j][i] & (1<<k))
                    printf("%d ",k+1);
            }
            printf("\n");
        }
        printf("\n\n\n======\n\n\n");
    }
    return 0;
}

最初的回答：这是您在寻找的内容吗？

- himanshu tiwari

---

嗨Himanshu...让我把你的代码转换成JS，如果成功了我会告诉你。 - Faizan

好的，但你也可以通过在C++中运行此代码来检查输出。 - himanshu tiwari

Answer 2

一个选项是先将列表分成相同数字的组，然后按长度排序。然后，您可以通过从最长、第二长、第三长、第四长开始取每个组的元素来创建组。当您清空一个子组时，请将其删除。

以下是JS实现：

一个选择是先将列表分成相同数字的组，然后按长度排序。然后，您可以通过从最长、第二长、第三长、第四长开始取每个组的元素来创建组。当您清空一个子组时，请将其删除。

function partition(arr, N){
    // group items together and sort by length
    // groups will be [[5, 5, 5, 5, 5], [4, 4, 4, 4], ...]

    let groups = Object.values(l.reduce((obj, n) =>{
        (obj[n] || (obj[n] = [])).push(n)
        return obj
    }, {})).sort((a,b) => b.length - a.length)

    let res = []
    while(groups.length >= N){
        let group = []
        let i = 0
        while (group.length < N){
           group.push(groups[i].pop())
           if (groups[i].length < 1) groups.splice(i, 1)
           else i++
        }
        res.push(group)
    }
    return res
}
let l = [1,2,3,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,9,10,10,11,12,13,13,14,14,15,16,17,17]


console.log(partition(l, 4).map(arr => arr.join(',')))

// with 5
console.log(partition(l, 5).map(arr => arr.join(',')))

- Mark

---

嗨，马克。非常感谢你的努力，但是每次运行它都会给我相同的输出。我想在每次运行时生成一个随机排列。 - Faizan

我可能误解了。我以为你是通用解决方案，返回的顺序并不重要。这将返回最长的子列表数量，但始终是相同的。我似乎错过了这一行：“每次运行程序时，我只需要生成一个随机排列”。 - Mark

Answer 3

以下Python代码每次运行都使用一种简单的方法来生成随机分区。它对32个整数的列表进行洗牌（以获得随机结果），然后使用一种先适配+回溯的方法找到从该洗牌中得出的第一个排列。效率：此处使用的Fisher-Yates洗牌是O(n)算法。从洗牌中找到第一个排列可能接近于O(n)，也可能远远超过，这取决于原始数字和洗牌，如下所述。

注意事项：理想情况下，不同的洗牌应该导致不同的分区。但是这不可能，因为有比不同分区更多的不同洗牌（大约10的20次方倍的洗牌与分区）。理想情况下，每个可能的分区应该具有相等的被生成的概率。我不知道在这里是否是这种情况，甚至不知道这种方法是否涵盖了所有可能的分区。例如，可能存在一些分区无法通过先适配+回溯的方法生成。

虽然该方法在大多数情况下可以快速生成解决方案，例如在一毫秒以内，但有时会因为在递归的早期发生冲突而浪费很多时间，而这些冲突直到几层深度后才被检测出来。例如，寻找四组1000个不同解决方案的时间分别为96秒、166秒、125秒和307秒，而寻找100个不同解决方案的时间包括56毫秒、78毫秒、1.7秒、5秒、50秒。

一些程序注释：在洗牌列表s中，我们保存2的mn-k次方而不是k。使用数据的位掩码而不是计数数字可以加快重复测试。指数mn-k（在2的mn-k次方中）使数组u排序，以便输出按升序排列。在Python中，#引入注释。带有for表达式的括号表示“列表推导”，一种用for语句生成列表的方式。表达式[0]*nc表示一个具有nc个元素的列表或数组，最初全部为0。

from random import randint
A = [1,2,3,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,
     9,10,10,11,12,13,13,14,14,15,16,17,17] # Original number list
ns = len(A)                     # Number of numbers
nc = 8                          # Number of cells
mc = 4                          # Max cell occupancy
rc = range(nc)                  # [0,1,...nc-1]
mn = max(A)                     # Max number 
s = [ 2**(mn-k) for k in A]

for i in range(ns-1,0,-1):
    j = randint(0,i)
    s[i], s[j] = s[j], s[i]     # Do a shuffle exchange

# Create tracking arrays: n for cell count, u for used numbers.
n = [0]*nc
u = [0]*nc

def descend(level):
    if level == ns:
        return True
    v = s[level]        # The number we are trying to place
    for i in rc:
        if (v & u[i] == 0) and n[i] < mc:
            u[i] |= v           # Put v into cell i
            n[i] += 1
            if descend(level+1):
                return True     # Got solution, go up and out
            else:
                u[i] ^= v       # Remove v from cell i
                n[i] -= 1
    return False                # Failed at this level, so backtrack

if descend(0):
    for v in sorted(u, reverse=True):
        c = [ mn-k for k in range(mn+1) if v & 2**k]
        print (sorted(c))
else:
    print ('Failed')

一些示例输出：

[1, 2, 5, 9]
[3, 4, 6, 14]
[4, 5, 6, 10]
[4, 5, 7, 17]
[4, 10, 15, 16]
[5, 7, 8, 17]
[5, 7, 11, 13]
[7, 12, 13, 14]

[1, 4, 7, 13]
[2, 5, 7, 8]
[3, 4, 5, 17]
[4, 5, 6, 14]
[4, 6, 7, 9]
[5, 10, 11, 13]
[5, 10, 12, 16]
[7, 14, 15, 17]

- James Waldby - jwpat7

Answer 4

这里展示了枚举集合所有可能性的演示（不是像你的示例中那样的多重集合），只是为了展示组合数量迅速增加的方式。对于8个4元素部分的分区，组合数量将是巨大的。我不确定，但您可能可以采用其中一些想法来结合多重集合，或者至少先进行部分枚举，然后随机添加重复元素。

function f(ns, subs){
  if (ns.length != subs.reduce((a,b) => a+b))
    throw new Error('Subset cardinality mismatch');

  function g(i, _subs){
    if (i == ns.length)
      return [_subs];

    let res = [];
    const cardinalities = new Set();

    function h(j){
      let temp = _subs.map(x => x.slice());
      temp[j].push(ns[i]);
      res = res.concat(g(i + 1, temp));
    }

    for (let j=0; j<subs.length; j++){
      if (!_subs[j].length && !cardinalities.has(subs[j])){
        h(j);
        cardinalities.add(subs[j]);

      } else if (_subs[j].length && _subs[j].length < subs[j]){
        h(j);
      }
    }
    return res;
  }
  let _subs = [];
  subs.map(_ => _subs.push([]));

  return g(0, _subs);
}

// https://oeis.org/A025035
let N = 12;
let K = 3;

for (let n=K; n<=N; n+=K){
  let a = [];
  for (let i=0; i<n; i++)
    a.push(i);
  let b = [];
  for (let i=0; i<n/K; i++)
    b.push(K);
  console.log(`\n${ JSON.stringify(a) }, ${ JSON.stringify(b) }`);

  let result = f(a, b);
  console.log(`${ result.length } combinations`);

  if (n < 7){
    let str = '';
    for (let i of result)
    str += '\n' + JSON.stringify(i);
    console.log(str);
  }

  console.log('------');
}

- גלעד ברקן

---

嗨גלעד ברקן，让我调整你的代码来完成我的任务，如果可行我会告诉你。 - Faizan