Find a subset of consecutive numbers made up of K

Question

Help with the solution of the problem.

In the array, find a subset of consecutive numbers (elements cannot be rearranged) composed of K not necessarily adjacent elements of the array (there may be several such subsets). Type array elements.

It is necessary to modify this code.

#include "stdafx.h" #include <stdio.h> #include <conio.h> #include "testing.h" int main() { int length_subset = 0; //длина искомого подмножества int max_length_subset = 0; //длина максимального подмножества int start_subset = 0; //начало искомого множества в исходном массиве(переменная содержит адрес элемента массива,с которого начинается искомое множество) int original_subset[20]; //исходный массив чисел int result_subset[20]; //массив, в котором будут хранится значения искомой последовательности int k = 0, j = 0, count_subset = 0; //счетчики int end_subset; //конец искомого подмножества в исходном массиве(переменная содержит адрес элемента массива,на котором заканчивается искомое множество) int quantity_elements; // количество элементов подмножества int m = 0; //длина массива //Ввести длину массива //Вывести на экран сообщение "Enter lenght of array: " input_printf("Enter lenght of array: "); scanf_s("%d", &m); //Проверить ее корректность if (m < 2 || m > 20) { //Вывести на экран сообщение "No solution" printf("Invalid input data"); WAIT_ANY_KEY return 0; } //Ввести элементы массива for (int i = 0; i < m; i++) { //Вывести на экран сообщение "Enter element of array: " input_printf("Enter element of array: "); scanf_s("%d", &original_subset[i]); //Проверить их корректность if (original_subset[i] > 1000 || original_subset[i] < -1000) { //Вывести на экран сообщение "No solution" error_printf("Invalid input data"); WAIT_ANY_KEY return 0; } } //Найти максимальные подмножества последовательных чисел в данном массиве //Для всех элементов массива for (int i = 0; i < m; i++) { j = i; length_subset = 0; start_subset = 0; //Пока текущий элемент массива + 1 = следующему элементу массива while ((original_subset[j] + 1) == (original_subset[j + 1])) { ++length_subset; //увеличить длину искомого подмножества на единицу j++; if (start_subset == 0) //условие для того,чтобы переменная инициализировалась только один раз { start_subset = i; } } ++length_subset; //увеличить длину, т.к. для последнего члена условие while не выполняется //Определить конец удаляемой последовательности end_subset = start_subset + length_subset; //конец удаляемой последовательности //Если текущее количество = максимальному количеству if (max_length_subset == length_subset && max_length_subset > 1) //искомые множества равны, записать и оставить предыдущее { //Записать значения элементов в результирующий массив for (start_subset; start_subset < end_subset; start_subset++) { result_subset[k] = original_subset[start_subset]; k++; //k здесь не меняется изначально, записывать начнет с того места, где было записано последнее } quantity_elements += length_subset; //увеличить количество элементов, т.к. добавлено множество } //Если текущее количество > максимального количества else if (max_length_subset < length_subset && length_subset > 1) { max_length_subset = length_subset; //присвоить текущее значение максимальному k = 0; //k здесь обнуляется, т.к. найдено большее множество и нужно записать только его и сначала //Записать значения элементов в результирующий массив for (start_subset; start_subset < end_subset; start_subset++) { result_subset[k] = original_subset[start_subset]; k++; } quantity_elements = length_subset; //обновить количество элементов } } //Если в массиве нет подмножеств //Если число последовательных элементов в подмножестве равно 0 if (max_length_subset == 0) { //Вывести на экран сообщение "No solution" printf("no solution"); WAIT_ANY_KEY return 0; } //Вывести результирующие подмножества else { printf("\n\n\n"); //переход на 3 строки вниз //Вывести все элементы подмножеств for (k = 0; k < quantity_elements; k++) { //Вывести на экран текущий элемент массива printf("%d ", result_subset[k]); count_subset++; //Выполнить перенос строки через максимальное количество элементов в подмножестве if (count_subset == max_length_subset) { printf("\n"); count_subset = 0; } } WAIT_ANY_KEY return 0; } }

Do not put the necessary information for the answer in the comments, edit your question instead.
@jfs I see a problem that I don’t understand how to implement it, because in my code the subsets are sequentially behind them, and here they may not be in the neighborhood.

Answer 1 · 2017-04-17T16:59:52

Two algorithms: one rectilinear quadratic O(n**2) , and the other optimal single pass O(n) .

O (n ** 2) in time, O (k) in memory algorithm

Algorithm: for each element in the array X , we build subsequences starting with this element and consisting of consecutive numbers (but the indices may not be consecutive) until the length of the subsequence is equal to the desired one (they did not find a solution).

The current subsequence is represented by an array of indices M such that

 X[M[i]] + 1 == X[M[i+1]]

for all possible i (expresses the condition of a sequence of numbers):

 #include <stdbool.h> #include <stdlib.h> /** Fill *M* such that: all(X[M[i]] == X[M[i+1]] - 1 for i in range(k-1)). * * Return whether found the natural subsequence (managed to fill *M*). */ bool find_natural_subsequence(int *X, size_t n, int* M, size_t k) { if (k == 0) return true; /* empty result (M), do nothing */ else if (k == 1) { if (n > 0) { M[0] = 0; /* [X[0]]: any subsequence with one item will do */ return true; } } else { /* k > 1 */ for (size_t i = 0; i < n; ++i) { size_t last = 0; /* index of the last filled M value */ M[last] = i; /* check the subsequence starting here */ for (size_t j = i + 1; j < n; ++j) { if (X[M[last]] == X[j] - 1) { /* found the next item */ M[++last] = j; if (last == k-1) return true; /* found the subsequence */ } } } } return false; /* not found */ }

This is a quadratic algorithm ( O(n**2) time, O(k) memory for the result). Example:

 #include <stdio.h> int main(void) { int k = 4; int X[] = {-7, 1, 3, 4, -2, 2, 5, 6}; int M[k]; if(find_natural_subsequence(X, sizeof(X)/sizeof(*X), M, k)) { for (int i = 0; i < k; ++i) printf("%d ", X[M[i]]); putchar('\n'); return 0; } fputs("not found\n", stderr); exit(EXIT_FAILURE); }

Result:

 $ cc *.c && ./a.out 3 4 5 6

O (n) time and memory algorithm

You can improve the algorithm and make it O(n) (linear one-pass) using O(n) memory (the stack here is like a stack of cards, in which we see the value of only the most recent (top) card):

If the input size is zero, then we return an empty list.
For each item in the collection, we take out the stack where the item is one more than the top of the stack in order to get consecutive numbers in each stack. If you have not found a suitable stack, then create a new empty stack.
Add an item to the stack (up, last)
If the stack size is equal to the required one, then we return it.
We add a stack back, indexing on a new last element. If the seat is already taken, then we leave a higher (long) stack.

On Python, this can be expressed as:

 def find_natural_subsequence(iterable, size): if size == 0: return [] # 1. empty pile piles = {} # mapping: <top of the pile> -> pile for x in iterable: # 2. extract the pile where we can put `x`: <top of the pile> + 1 == x pile = piles.pop(x-1, []) # O(1) # 3. add x to the pile (push on top) pile.append(x) # O(1) # 4. found the subsequence if len(pile) == size: return pile # 5. put it back piles[x] = max(pile, piles.pop(x, ()), key=len) # O(1) raise ValueError((iterable, size))

Example:

 >>> find_natural_subsequence([-7, 1, 3, 4, -2, 2, 5, 6], 4) [3, 4, 5, 6]

Here is a visualization that shows how the stacks (stacks) represented by the piles in the code grow .

For C ++ implementation, you can use std::unordered_map to represent piles and std::vector for each stack.

Find a subset of consecutive numbers made up of K

1 answer 1

O (n ** 2) in time, O (k) in memory algorithm

O (n) time and memory algorithm

More articles: