Поиск подмассива с заданной суммой
Условие: Дано целочисленное множество (массив) чисел и целое число S. Найдите все уникальные подмассивы, сумма которых равна S.
Пример входных данных:
Массив: [1, 2, 3, 4, 5]
S: 5
Ожидаемый результат:
[[1, 4], [2, 3], [5]]
Убедитесь, что вы сохраняете только уникальные подмассивы.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] array = { 1, 2, 3, 4, 5 };
int S = 5;
var result = FindUniqueSubarrays(array, S);
// Вывод результата
foreach (var subarray in result)
{
Console.WriteLine($"[{string.Join(", ", subarray)}]");
}
}
static List<List<int>> FindUniqueSubarrays(int[] arr, int S)
{
HashSet<string> uniqueSubarrays = new HashSet<string>();
Ответы (2 шт):
Pешение:
В файле с данными "input*.txt" (значение звёздочки задаётся в командной строке) на первом месте - искомая сумма:
7 1 2 3 4 5 6 7
using System; using System.IO; using System.Collections.Generic;
public class ReverseComparer : IComparer<int> {
public int Compare(int x, int y) { return y.CompareTo(x); }
}
class Cell {
public int i; public Cell cell;
public Cell(Cell cell, int i) { this.cell = cell; this.i = i; }
}
static class Program {
static int[] arr; static int le; static int counter; static int arrmax;
static void GetSum(int sum, int ind, Cell cll) {
for (int i = ind, prev = arrmax; i < le; prev = arr[i++])
if (arr[i] == prev) { }
else if (arr[i] == sum) {
counter++; var cl = new Cell(cll, sum);
do Console.Write("{0} ", cl.i); while ((cl = cl.cell).cell != null);
Console.WriteLine();
}
else if (arr[i] < sum) GetSum(sum - arr[i], i + 1, new Cell(cll, arr[i]));
}
static void Main(string[] args) {
arr = Array.ConvertAll(File.ReadAllText("input" + args[0] + ".txt").Split(' '),
Convert.ToInt32); counter = 0; le = arr.Length;
Array.Sort(arr, 1, le - 1, new ReverseComparer()); arrmax = arr[1] + 1;
GetSum(arr[0], 1, new Cell(null, 0)); Console.WriteLine(counter);
}
}
Результат:
7
1 6
2 5
3 4
1 2 4
Если нужно и с отрицательными числами, то необходима дополнительная сортировка:
static void Main(string[] args) {
arr = Array.ConvertAll(File.ReadAllText("input" + args[0] + ".txt").Split(' '),
Convert.ToInt32); counter = 0;
le = arr.Length; Array.Sort(arr, 1, le - 1);
int i = 1; while (arr[i] < 0) i++;
Array.Sort(arr, i, le - i, new ReverseComparer());
arrmax = arr[1] + (arr[1] > 0 ? 1 : -1);
GetSum(arr[0], 1, new Cell(null, 0)); Console.WriteLine(counter);
}
Та же программа, но с ООПэшными плюшками и перечислителями:
using System; using System.IO; using System.Collections.Generic;
public class ReverseComparer : IComparer<int> {
public int Compare(int x, int y) { return y.CompareTo(x); }
}
class Cell {
int i; Cell cell;
Cell(Cell cell, int i) { this.cell = cell; this.i = i; }
public static Cell First => new Cell(null, 0);
public Cell Next(int i) => new Cell(this, i);
IEnumerable<int> GetValues() {
var cll = this;
do if (cll.cell != null) yield return cll.i; else yield break;
while ((cll = cll.cell) != null);
}
public override string ToString() => "[" + String.Join(", ", GetValues()) + "]";
}
static class Program {
static int[] arr; static int le; static int counter; static int arrmax;
static IEnumerable<string> GetSum(int sum, int ind, Cell cll) {
int prev = arrmax, j = arr[ind];
for (int i = ind; i < le; prev = j, j = arr[++i])
if (j == prev) { }
else if (j == sum) { counter++; yield return cll.Next(j).ToString(); }
else if (j < sum)
foreach (var s in GetSum(sum - j, i + 1, cll.Next(j)))
yield return s;
if (j != prev && j == sum) { counter++; yield return cll.Next(j).ToString(); }
if (ind == 1) yield break;
}
static void Main(string[] args) {
arr = Array.ConvertAll(File.ReadAllText("input" + args[0] + ".txt").Split(' '),
Convert.ToInt32); counter = 0; le = arr.Length - 1;
Array.Sort(arr, 1, le, new ReverseComparer()); arrmax = arr[1] + 1;
Console.WriteLine("[" +
String.Join(", ", GetSum(arr[0], 1, Cell.First)) + "]");
Console.WriteLine(counter);
}
}
Результат:
[[7], [1, 6], [2, 5], [3, 4], [1, 2, 4]]
5
Долгая получилась история.
Ваш дизайн предполагает что функция возвращает все решения одним списком. Но это комбинаторный поиск, который легко приводит комбинаторному взрыву. Если решений много, их надо будет долго ждать и для хранения понадобится много памяти. Я ввёл функцию обратного вызова, которая вызывается как только найдено очередное решение. Его можно распечатать или обработать как-то ещё, поиск можно прервать исключением. Наконец, можно написать обёртку, которая соберёт все решения в список. Всё в вашей воле.
Функция обрабатывает массив как мультимножество. Сам поиск устроен так, что варианты не повторяются, отдельная структура для устранения дублирования ответов не нужна.
Для скорости поиск не использует динамическую память. Я имею ввиду, что во время поиска никакие объекты не выделяются и не удаляются.
Отрицательные числа поддержаны.
Слагаемые перебираются от больших по модулю к меньшим. Сделано отсечение по суммам: на каждом шаге поиска проверяется что искомая сумма ещё может быть составлена из оставшихся элементов мультимножества.
Для удобства тестирования сделан ввод данных из консоли.
group по массиву строит мультимножество – пару массивов, в первом величины, во втором количество их повторений. Для скорости работы массивы упорядочены по росту абсолютных величин.
search ищет все сочетания слагаемых, которые дают заданную сумму. Если сочетание найдно, вызывает функция обратного вызова.
print – пример функции обратного вызова. Печатает слагаемые.
main считывает данные из консоли и запускает поиск.
using System;
using System.Linq;
(int[], int[]) group(int[] aa) {
int compare(int x, int y) {
int c_abs = Math.Abs(x).CompareTo(Math.Abs(y));
return (c_abs != 0) ? c_abs : x.CompareTo(y);
}
aa = (int[])aa.Clone();
Array.Sort(aa, compare);
int n = (aa.Length > 0) ? 1 : 0;
for (int i = 1; i < aa.Length; ++i) {
if (aa[i] != aa[i - 1]) {
++n;
}
}
int[] a = new int[n];
int[] e = new int[n];
int j = 0;
if (n > 0) {
a[j] = aa[0];
}
foreach (int aa_i in aa) {
if (aa_i != a[j]) {
++j;
a[j] = aa_i;
}
++e[j];
}
return (a, e);
}
void search(int[] aa, int target, Action<int, int[]> callback) {
(int[] a, int[] e) = group(aa);
int[] min = new int[a.Length];
int[] max = new int[a.Length];
for (int i = 0; i < a.Length; ++i) {
min[i] = ((i == 0) ? 0 : min[i - 1]) + Math.Min(0, e[i] * a[i]);
max[i] = ((i == 0) ? 0 : max[i - 1]) + Math.Max(0, e[i] * a[i]);
}
int[] b = new int[e.Sum()];
void search(int i, int s, int j) {
if (i < 0) {
if (s == 0) {
callback(j, b);
}
} else if (min[i] <= s && s <= max[i]) {
search(i - 1, s, j);
for (int k = e[i]; k > 0; --k) {
b[j] = a[i];
++j;
s -= a[i];
search(i - 1, s, j);
}
}
}
search(a.Length - 1, target, 0);
}
void print(int n, int[] a) {
for (int i = 0; i < n; ++i) {
Console.Write($"{a[i]}{((i == n - 1) ? '\n' : ' ')}");
}
}
void main() {
int target = int.Parse(Console.ReadLine());
string[] words = Console.ReadLine().Split(' ');
int[] a = new int[words.Length];
for (int i = 0; i < words.Length; ++i) {
a[i] = int.Parse(words[i]);
}
search(a, target, print);
}
main();
Тестовый пример из вопроса:
$ csc /nologo 4.cs $ echo -e "5\n1 2 3 4 5" | mono 4.exe 3 2 4 1 5
Все представления сотни в фибоначчиевой системе счисления:
$ echo -e "100\n1 1 2 3 5 8 13 21 34 55 89 144" | mono 4.exe 55 21 13 5 3 2 1 55 21 13 8 2 1 55 21 13 8 3 55 34 5 3 2 1 55 34 8 2 1 55 34 8 3 89 5 3 2 1 89 8 2 1 89 8 3
Сотня в двоичной системе счисления:
$ echo -e "100\n1 2 4 8 16 32 64 128" | mono 4.exe 64 32 4
Проверка решения из соседнего вопроса:
$ echo -e "9002\n11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999" | mono 4.exe 3333 1111 999 777 666 555 444 333 222 111 99 88 77 66 55 33 22 11 3333 1111 999 777 666 555 444 333 222 111 99 88 77 66 55 44 22 3333 1111 999 888 666 555 444 333 222 99 88 77 66 55 33 22 11 3333 1111 999 888 666 555 444 333 222 99 88 77 66 55 44 22 3333 1111 999 888 777 555 444 333 111 99 88 77 66 55 33 22 11 3333 1111 999 888 777 555 444 333 111 99 88 77 66 55 44 22 3333 1111 999 888 777 666 444 222 111 99 88 77 66 55 33 22 11 3333 1111 999 888 777 666 444 222 111 99 88 77 66 55 44 22 3333 1111 999 888 777 666 444 333 99 88 77 66 55 33 22 11 3333 1111 999 888 777 666 444 333 99 88 77 66 55 44 22 3333 1111 999 888 777 666 555 222 99 88 77 66 55 33 22 11 3333 1111 999 888 777 666 555 222 99 88 77 66 55 44 22 4444 999 777 666 555 444 333 222 111 99 88 77 66 55 33 22 11 4444 999 777 666 555 444 333 222 111 99 88 77 66 55 44 22 4444 999 888 666 555 444 333 222 99 88 77 66 55 33 22 11 4444 999 888 666 555 444 333 222 99 88 77 66 55 44 22 4444 999 888 777 555 444 333 111 99 88 77 66 55 33 22 11 4444 999 888 777 555 444 333 111 99 88 77 66 55 44 22 4444 999 888 777 666 444 222 111 99 88 77 66 55 33 22 11 4444 999 888 777 666 444 222 111 99 88 77 66 55 44 22 4444 999 888 777 666 444 333 99 88 77 66 55 33 22 11 4444 999 888 777 666 444 333 99 88 77 66 55 44 22 4444 999 888 777 666 555 222 99 88 77 66 55 33 22 11 4444 999 888 777 666 555 222 99 88 77 66 55 44 22