如何从特定的单个数组中找到所有不重复的组合使用 Javascript

Question

我是一个 Javascript 初学者，我有一个个人项目使用程序来查找特定数组的所有可能且没有重复的组合

我假设有 3 套产品，每套 10 种款式，就像这个数组

[1,2,3,4..10,1,2,4...8,9,10]

①②③④⑤⑥⑦⑧⑨⑩
①②③④⑤⑥⑦⑧⑨⑩
①②③④⑤⑥⑦⑧⑨⑩

总共数组长度 = 30

我打算随机分成5个children，但是不能重复相同的产品款式

好的结果： ①②③④⑤⑥ ✔ ②③④⑤⑥⑦ ✔ ①②③⑧⑨⑩ ✔ ④⑥⑦⑧⑨⑩ ✔ ①⑤⑦⑧⑧⑩ ✔

大家可以平均分配不重复的产品

错误： ①②③④⑤⑥ ✔ ①②③④⑤⑦ ✔ ①②⑥⑧⑩⑩ ✔ ③④⑤⑦⑧⑨ ✔ ⑥⑦⑧⑨⑩⑩✘（因为数字10重复了）

我的方案是随机分配5组数组，然后使用“new Set(myArray[i]).size;”检查值 sum 是否为 30，使用 [do..white]，当 sum 不是 30 时，然后重复执行随机分配函数，直到结果不重复。

像这样：

function splitArray() {
  
    do {
      var productArray = [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10];  //Just for sample, actualy this array will be more then 30
      var productPerChildArray = [];
      for (var i = 0; i < 5; i++) {
        GroupNum = [];
  
        for (var v = 0; v < 6; v++) {
          var selectNum = productArray[Math.floor(Math.random() * productArray.length)];
          GroupNum.push(selectNum);
          productArray = removeItemOnce(productArray, selectNum);
        }
  
        productPerChildArray.push(GroupNum);
      }
    } while (checkIfArrayIsUnique(productPerChildArray));
  
    return productPerChildArray;
  }
  
  //---------check repeat or not----------
  function checkIfArrayIsUnique(myArray) {
    var countRight  = 0;
    for (var i = 0; i < myArray.length; i++) {
      countRight += new Set(myArray[i]).size;
    }
    return (countRight != 5*6);
  }

  //----------update productArray status----------
function removeItemOnce(arr, value) {
    var index = arr.indexOf(value);
    if (index > -1) {
      arr.splice(index, 1);
    }
    return arr;
  }

  console.log(splitArray());

看似解决了问题，但实际上productArray不一定是30，这个解决方案会花很多时间去尝试no repeat组合。低效率

我相信他们有比我的想法更好的解决问题的方法

如有任何帮助，我们将不胜感激。

Answer 1

我的方法是：将下一个数字放入随机选择的 array - 当然，过滤掉那些已经包含下一个数字的数字。

// the beginning dataset
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// the size of the groups to be formed (must divide the
// size of beginning dataset without a remainder)
const ARR_LENGTH = 6

// creating the array that will be filled randomly
const getBaseArray = ({ data, arrLength }) => {
  const num = parseInt(data.length / arrLength, 10)
  return Array.from(Array(num), () => [])
}

// filter arrays that satisfy conditions
const conditions = ({ subArr, val }) => {
  if (subArr.includes(val)) return false
  if (ARR_LENGTH <= subArr.length) return false
  return true
}
const getArraysFiltered = ({ val, arr }) => {
  return arr
    .map((e, i) => ({
      origIdx: i,
      subArr: e,
    }))
    .filter(({ subArr }) => conditions({ subArr, val }))
}

// select a random array from a list of arrays
const getRandomArrIdx = ({ arr }) => {
  return Math.floor(Math.random() * arr.length)
}

// get the original array index from the filtered values
const getArrIdx = ({ val, arr }) => {
  const filtered = getArraysFiltered({ val, arr })
  if (!filtered.length) return -1

  const randomArrIdx = getRandomArrIdx({ arr: filtered })
  return filtered[randomArrIdx].origIdx
}

const getFinalArr = ({ data }) => {
  // short circuit: if the data cannot be placed in
  // arrays evenly, then it's a mistake (based on
  // the current ruleset)
  if (data.length % ARR_LENGTH) return [false]

  // creating the array that will hold the numbers
  const arr = getBaseArray({ data, arrLength: ARR_LENGTH })
 
  let i = 0;
  for (i; i < data.length; i++) {
    const idx = getArrIdx({
      val: data[i],
      arr,
    })
    // if there's no place that the next number could be
    // placed, then break (prematurely), so the algorithm
    // can be restarted as early as possible
    if (idx === -1) break;
    arr[idx].push(data[i])
  }

  if (i < data.length) {
    // restart algorithm if we couldn't place
    // all the numbers in the dataset
    return getFinalArr({ data })
  } else {
    return arr
  }

}

// constructing the final array of arrays & logging them:
console.log('res', getFinalArr({ data }).join(' '))
console.log('res', getFinalArr({ data }).join(' '))
console.log('res', getFinalArr({ data }).join(' '))
console.log('res', getFinalArr({ data }).join(' '))

不知道是不是更有效率，不过觉得这个问题很有意思

现在，算法是

分解成小的逻辑步骤
易于理解
易于根据需要进行调整
适用于所有大小的数据（如果要制作的组可以平均填充）

如何从特定的单个数组中找到所有不重复的组合使用 Javascript

How to find all no repeat combinations form specific single arrays use Javascript

javascript

arrays

combinations

duplicates