Как сгенерировать всю подпоследовательность четной длины из массива?

Question

Я имею дело с проблемой, и эта проблема требует ответа на эту подпрограмму. Я знаю, как генерировать все подпоследовательности из массива, используя битовые манипуляции, но изо всех сил пытался генерировать подпоследовательности четной длины.

Для примера предположим, что существует массив A = [2, 5, 4, 2, 3, 1]

Я хочу, чтобы все подпоследовательности были четной длины, то есть длины 2, 4 и 6.

Правка 1: 1<=N<=1000, где N - размер массива.

Answer 1

#include <stdio.h>
#define N 4

const int A[] = { 2, 5, 4, 2, 3, 1, -1 };
int out[1000];

void gen(const int *p, int *pout) {
  if(pout - out < N) {
    while((*pout = *p++) > 0)
      gen(p, pout + 1);
  } else { // print output
    for(const int *o = out; o < pout; o++)
      printf("%d ", *o);
    putchar('\n');
  }
}

int main(int argc, char **argv) {
  gen(A, out);
  return 0;
}

Answer 2

Поскольку вы уже знаете, как генерировать все подпоследовательности, просто удалите последний элемент и сгенерируйте все подпоследовательности оставшегося массива, но добавьте последний обратно к каждой подпоследовательности с нечетной длиной.

Легко доказать, что это генерирует все подпоследовательности четной длины:

• Каждая подпоследовательность четной длины A, которая не заканчивается в последнем элементе A, является подпоследовательностью четной длины более ранних элементов.
• Каждая подпоследовательность четной длины A, которая заканчивается в последнем элементе A, имеет этот элемент, которому предшествует подпоследовательность нечетной длины более ранних элементов.

Answer 3

Подмассивы

Используя функции генератора, вы можете воспользоваться преимуществами отложенного выполнения для итерации всех четных подмассивов без сохранения всей коллекции подмассивов в памяти:

function * subarrays (array) {
  for (let length = 1; length <= array.length; length++) {
    for (let index = 0; index + length <= array.length; index++) {
      yield array.slice(index, index + length);
    }
  }
}

const filter = predicate => function * (iterator) {
  for (const value of iterator) {
    if (predicate(value)) yield value;
  }
};

const even = filter(subarray => subarray.length % 2 === 0);


for (const subarray of even(subarrays ([2, 5, 4, 2, 3, 1]))) {
  console.log(subarray.join());
}

Однако, если вы хотите получить всю коллекцию четных подмассивов, вы можете использоватьArray.from() потреблять итератор и заполнять массив подмассивов:

function * subarrays (array) {
  for (let length = 1; length <= array.length; length++) {
    for (let index = 0; index + length <= array.length; index++) {
      yield array.slice(index, index + length);
    }
  }
}

const filter = predicate => function * (iterator) {
  for (const value of iterator) {
    if (predicate(value)) yield value;
  }
};

const even = filter(subarray => subarray.length % 2 === 0);
const result = Array.from(even(subarrays([2, 5, 4, 2, 3, 1])));

console.log(JSON.stringify(result));

подпоследовательности

Для итерации всех четных подпоследовательностей одним из самых простых способов является ведение таблицы поиска, значения которойfilter() из массива. Мы можем достичь этого с минимальными затратами памяти, используя Uint32Array:

function _increment (uint32Array) {
  for (let index = 0; index < uint32Array.length; index++) {
    // use unsigned integer overflow to
    // perform carry in base 2**32 addition
    if (++uint32Array[index]) return;
  }
}

function * subsequences (array) {
  const lut = new Uint32Array(Math.ceil(array.length / 32));
  let subsequence;

  while (true) {
    yield subsequence = array.filter(
      (_, index) => (lut[index >>> 5] >>> (index % 32)) & 1
    );

    if (subsequence.length === array.length) return;
    _increment(lut);
  }
}

const filter = predicate => function * (iterator) {
  for (const value of iterator) {
    if (predicate(value)) yield value;
  }
};

const even = filter(({ length }) => (length > 0) && (length % 2 === 0));

for (const subsequence of even(subsequences([2, 5, 4, 2, 3, 1]))) {
  console.log(subsequence.join());
}

Answer 4

Вот Python, который так же хорош, как псевдокод:

def even_subsequences(L): 
    # yield the empty subsequence
    yield []

    # iterate over subsequence starting points
    for i in range(len(L)): 
        # subsequence end point is the starting point plus an even number
        for j in range(i+2, len(L)+1, 2):
            # slice the list
            yield L[i:j] 


>>> list(even_subsequences([1,2,3,4,5,6]))
[[],
 [1, 2],
 [1, 2, 3, 4],
 [1, 2, 3, 4, 5, 6],
 [2, 3],
 [2, 3, 4, 5],
 [3, 4],
 [3, 4, 5, 6],
 [4, 5],
 [5, 6]]