如何确定值的块是否适合数组

Given an input array of 1s and 0s of arbitrary length, such as:

给定1s和0s任意长度的输入数组,例如:

[0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

How can I (most efficiently) calculate a new array detailing if chunks of size n 0s which can fit into the input?

我如何(最有效)计算一个新的数组详细说明如果大小为n 0的块可以适合输入?

Examples

Where output now means

输出现在意味着什么

1 == 'Yes a zero chunk that size could go here'

1 =='是一个零块,大小可以到这里'

0 == 'Couldn't fit a chunk that size there'

0 =='无法放入那么大的块

Chunk size = 1 ([0]): [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]

块大小= 1([0]):[1,0,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,1]

Chunk size = 2 ([0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]

块大小= 2([0,0]):[0,0,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,1 ]

Chunk size = 3 ([0,0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]

块大小= 3([0,0,0]):[0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0 ,0]

Chunk size = 4 ([0,0,0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

块大小= 4([0,0,0,0]):[0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ,0,0]

I'm using ES6, so any language features are fine.

我正在使用ES6,所以任何语言功能都很好。

EDIT:

The output shouldn't just be a 'yes'/'no' a chunk of size 'n' can fit in this array. More specifically, it needs to be an array of the same length, where a '1' / 'true' array value represents either:

输出不应该只是'是'/'不',大小'n'的大块可以放在这个数组中。更具体地说,它需要是一个长度相同的数组,其中'1'/'true'数组值代表:

Yes, a chunk of size 'n' could start and fit here, or

是的,一大块'n'可以开始并适合这里,或者

Yes, this slot could contain a chunk of size 'n' that started before it

是的,这个插槽可能包含一个在它之前开始的大小'n'的块

On that second point, this would mean for chunk size 3:

在第二点,这将意味着块大小3:

input = [1, 0, 0, 0, 0, 1];

input = [1,0,0,0,0,1];

output = [0, 1, 1, 1, 1, 0];

output = [0,1,1,1,1,0];

Edit 2:

This is the function I came up with but it seems very inefficient:

这是我想出的功能,但效果似乎非常低效:

const calculateOutput = (input, chunkSize) => {
  const output = input.map((value, index) => {
    let chunkFitsHere = false;

    const start = (index - (chunkSize) >= 0) ? index - (chunkSize) : 0;
    const possibleValues = input.slice(start, index + chunkSize);
    possibleValues.forEach((pValue, pIndex) => {
      let consecutives = 0;
      for (let i = 0; i < possibleValues.length - 1; i += 1) {
        if (consecutives === chunkSize) {
          break;
        }
        if (possibleValues[i+1] === 0) {
          consecutives += 1;
        } else {
          consecutives = 0;
        }
      }
      if (consecutives === chunkSize) {
        chunkFitsHere = true;
      }
    });
    return chunkFitsHere ? 1 : 0;
  });
  return output;
};

5 个解决方案

#1

You could count the connected free places by reversing the array and take an flag for the last return value for mapping.

您可以通过反转数组来计算连接的空闲位置,并为映射的最后一个返回值取一个标志。

Array before final mapping and after, depending on n

最终映射之前和之后的数组,取决于n

 1  0  4  3  2  1  0  0  2  1  0  0  0  3  2  1  0  2  1  array with counter
 1  0  4  4  4  4  0  0  2  2  0  0  0  3  3  3  0  2  2  array same counter
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --  ------------------
 1  0  1  1  1  1  0  0  1  1  0  0  0  1  1  1  0  1  1  n = 1
 0  0  1  1  1  1  0  0  1  1  0  0  0  1  1  1  0  1  1  n = 2
 0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  0  0  0  n = 3
 0  0  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  n = 4

function chunk(array, n) {
    return array
        .slice()
        .reverse()
        .map((c => v => v ? c = 0 : ++c)(0))
        .reverse()
        .map((l => v => l = v && (l || v))(0))
        .map(v => +(v >= n));
}

var array = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0];

console.log(chunk(array, 1).join(' '));
console.log(chunk(array, 2).join(' '));
console.log(chunk(array, 3).join(' '));
console.log(chunk(array, 4).join(' '));

If you like only one mapping at the end, remove the last two map and use

如果您最后只想要一个映射,请删除最后两个映射并使用

.map((l => v => l = +(v && (v >= n || l)))(0));

for final mapping.

用于最终映射。

#2

You can traverse array once, calculating length of the series of zeros. If it is long enough, fill output with series of 1 of the same length.

您可以遍历数组一次,计算一系列零的长度。如果足够长,请使用相同长度的1系列填充输出。

Note that you can fill output for different chunk lengths simultaneously (filling chunks in rows of 2d array with row index not exceeding zerolen)

请注意,您可以同时填充不同块长度的输出(在行索引不超过zerolen的情况下填充2d数组的行中的块)

Python code:

def zerochunks(a, n):
    l = len(a)
    result = [0] * l   #list of l zeros

    zerolen = 0
    for i in range(l + 1):
        ### Short circuit evaluation to shorten code
        if (i==l) or (a[i] != 0):   
            if (zerolen >= n):   #series of zeros is finished here
                for j in range(i - zerolen, i):
                    result[j] = 1
            zerolen  = 0
        else:
            zerolen += 1

    return result

print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 1))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 2))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 3))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 4))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 5))

>>> 
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

And function for getting all arrays with chunks in maxn range:

并且用于在maxn范围内获取具有块的所有数组的功能:

def zerochunksall(a, maxn):
    l = len(a)
    result = [[0] * l for i in range(maxn)]

    zerolen = 0
    for i in range(l + 1):
        if (i==l) or (a[i] != 0):
            for k in range(0, zerolen):
                for j in range(i - zerolen, i):
                    result[k][j] = 1
            zerolen  = 0
        else:
            zerolen += 1

    return result

print(zerochunksall([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 5))
 >>
[[1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1],
 [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1], 
 [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0], 
 [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

#3

function fit(input, n) {
    var output = [];
    for(var i = 0; i < input.length; i++) {
        var fit = true;
        for(var j = i; j < i + n; j++) {
            if(j >= input.length || input[j]) {  // either over the array size or occupied
                fit = false;
                break;
            }
        }
        output.push(fit);
    }
    return output;
}

var input = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0];
console.log(fit(input, 1).map(v => +v));
console.log(fit(input, 2).map(v => +v));
console.log(fit(input, 3).map(v => +v));
console.log(fit(input, 4).map(v => +v));

outputs

[ 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
[ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 ]
[ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

These don't seem to exactly match your expected output though, but that may be because I'm assuming the flags in the array should mark the start of the chunk (i.e. can you fit N truthy values in the array starting from this position).

这些似乎并不完全匹配您的预期输出,但这可能是因为我假设数组中的标志应该标记块的开始(即,您可以从此位置开始在数组中拟合N truthy值) 。

(See below, where e = your expected result, n = the output of my algorithm.)

(见下文,其中e =您的预期结果,n =我算法的输出。)

input = [ 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 ]
e = 2 = [ 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
n = 2 = [ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 ]
                         ====  ====  ====              ====

#4

You can use array.prototype.some to check if the chunk can fit starting to some index of the input array. To check if the chunk with it's actual length can fit, you can use array.prototype.every:

您可以使用array.prototype.some来检查块是否适合开始输入数组的某个索引。要检查具有实际长度的块是否适合,可以使用array.prototype.every:

var input = [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0];
var chunk = [0,0,0];
var res = input.some((e, i) => chunk.every((c, j) => input[i + j] === c));
console.log(res);

var input = [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0];
var chunk = [0, 0, 0, 0, 0, 0, 0, 0];
var res = input.some((e, i) => chunk.every((c, j) => input[i + j] === c));
console.log(res);

#5

You could use some method and then if the current element is 0 you can slice part of the array from current index and check if its all zeros.

您可以使用某种方法,然后如果当前元素为0,您可以从当前索引切片数组的一部分并检查它是否全部为零。

const data = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

function check(arr, n) {
  let chunk = Array(n).fill(0).join('');
  return arr.some((e, i) => e === 0 && arr.slice(i, i + n).join('') == chunk)
}

console.log(check(data, 3))
console.log(check(data, 4))
console.log(check(data, 5))

#1