欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

js实现在不重复的数组m中找到N位不重复的数的所有组合

程序员文章站 2022-03-13 12:28:23
...

原理比较简单,m数组中的每个数要么出现,要么不出现,只要满足n个数出现就可以了

算法步骤:

  1. 先生成一个和m数组一样长度的临时数组temp(数组中除了0,就是1),temp中值为1的表示m该在位置的数字出现,0则表示不出现。初始化temp,前n位为1,其他全为0。
  2. 每次从左往右遍历数组temp,遇到第一个10,就将其变成01,再将变化位置左边所有1移动到数组的最左边。输出(保存)当前数组temp,temp按照步骤1对应的位置为1的数组则为结果。
  3. 继续循环步骤2,一旦遇到temp为右边N位全为1时,结束循环。

构造一个对象用来生成所有的组合(对象中的getFlagArray方法): 

function findFlagArrays (opt) {
      let self = this
      let flag = {
        arr: opt.arr,
        n: opt.n,
        getFlagArray: function () {
          if(self.arr.length < self.n){
             console.log('寻找长度大于数组长度')
             return []
          }
          if(self.n < 1){
              return []
          }
          let len = this.arr.length
          let temp = []
          let jixu = true
          // 先给我们的数组初始化,前边n位为1,后边为0
          for (let i = 0; i < len; i++) {
            if (i < this.n) {
              temp.push(1)
            } else {
              temp.push(0)
            }
          }
          this.printf(temp)
          while (jixu) {
            let x = 0
            let y = 0
            let z = 0
            for (let i = 0; i < len - 1; i++) {
              if (temp[i] === 1 && temp[i + 1] === 0) {
                x = i
                temp[i] = 0
                temp[i + 1] = 1
                break
              }
            }
            for (let i = 0; i < x; i++) {
              if (temp[i] === 1) {
                y++
              }
            }

            for (let i = 0; i < x; i++) {
              if (i < y) {
                temp[i] = 1
              } else {
                temp[i] = 0
              }
            }
            this.printf(temp)
            // console.log(temp.join(' '))
            for (let i = 0; i < len; i++) {
              if (i < len - this.n && temp[i] === 0) {
                z++
              }
              if (i >= len - this.n && temp[i] === 1) {
                z++
              }
            }
            if (z === len) {
              jixu = false
            }
          }
        },
        printf: function (temp) {
          let result = []
          for (let i = 0; i < this.arr.length; i++) {
            if (temp[i] === 1) {
              result.push(this.arr[i])
            }
          }
          console.log(result.join(' ') + ' + ' + temp.join(' '))
        }
      }
      return flag
    }

调用实例:

function findZuhe () {
      let opt = {
        arr: [1, 2, 3, 4, 5, 6, 7],
        n: 4
      }
      let getFlag = this.findFlagArrays(opt)
      getFlag.getFlagArray()
    },