перебор с рекурсией

Отрезки случайные?

Да. Но их должно быть 120 штук. И длина одного отрезка не менее 1-го и не более 30-ти метров.

Спасибо, тоже так думал, но неужели нет более правильных вариантов?

knapsack но надо думать какой подойдет, по идее жадного хватит.

120/2 раза сформировать два отрезка: длиной (1000-2*120)/120 + 1 *X и (1000-2*120)/120 + 1 *( X - 1) где X - случайное число 0..1

ну, вообще-то частность - это вариант случайности.

1000/120 = 8 - вот тебе 120 отрезков по 8 метров. вполне себе быстрый способ.

Поправлю, 118 по 8м и 2 по 28м

ну можно поделить на четное количество отрезков, потом разделить на пары, для каждой пары(a, b) определить случайный «x» меньше длины равных отрезков, от одного отнять, другому прибавить (a+x, b-x).

А, ну рас у тебяеще лимиты, то можно и это учесть при поиске случайного. У тебя напиример 1 <= x + a <= 30 и 1 <= b - x <= 30

Привет. Допустим, есть отрезок длиной 1 000 метров. Необходимо его разбить на 120 отрезков. Новые отрезки должны быть не менее 1 метра и не более 30.
С помощью каких алгоритмов можно это реализовать?

Что именно ищешь: все возможные разбиения или какое-то одно разбиение?

Если первое, то задача предполагается целочисленной? Если второе, то чем не устраивает разбить поровну на 120 отрезков длиной 1000/120 метров каждый?

Разделение числа на заданное числа кусков разной длинны.

Итак, есть отрезок длиной X, нужно разбить на N частей длиной от Nmin до Nмах

1. находим допустимый Nmax=min(X-Nmin*(N-1), Nmax) 2. добавляем к разбиению случайный х' из [Nmin,Nmax] 3. X-=x', N-- 4. если N > 1 - перейти к шагу 1

понятно, что в полученном разбиении в начале элементы будут длиннее, чем в конце. От этого эффекта можно избавиться с помощью обычного перемешивания

координаты начал/концов целочисленные?

надо найти количество, вывести все (их много), вывести n-й, ещё что?

Разбей на 120 метровых отрезков. Потом, начиная с первого (нулевой оставим метровым) прибавляй случайное число от 0.1 до 29. Если выйдешь за пределы, пройдись по нескольким крупным и уменьши их, если недостача будет, разбей ее на несколько частей и прибавь к рандомным отрезкам.

Либо разделяй по формуле арифметической прогрессии с равноотстоящими членами. Потом можно будет рандомно от n-го отнять и к m-му прибавить.

Фактически тебе нужно сгенерировать 120 чисел от 1 до 30 так чтобы сумма была равна 1000. Вариантов куча, начиная с того что можно просто генерировать и считать сумму пока не получится как надо, и заканчивая полным перебором все возможных разбиений - возможных сумм 1000 не так уж много.

Если ещё интересно решение, то пиши завтра в Telegram (в профиле). Сейчас уже засыпаю, да и не хочу много писать с телефона.

тоже так думал, но неужели нет более правильных вариантов?

Как сказал один умный человек «when in doubt, use brute force» (c)

Пока ты сомневаешься, за 2 минуты накидал бы

$v = [];

for( $i=0; $i<120; $i++ ) $v[] = get_rand();

while( array_sum( $v ) != 1000 ) {
    array_shift( $v );
    $v[] = get_rand();
}

print_r( $v );

function get_rand()
{
    return rand(0,100) > 10 ? rand(1,16) : rand(1,30);
}

Метод перемешивания: разбиваешь свой отрезок на равные части. Отнимаешь от произвольного отрезка произвольное число и ЭТО ЖЕ число прибавляешь к другому случайному отрезку. После каждого шага проверяешь, что твои 2 отрезка не вышли за пределы. Ну или как-то реализуй проверку, это легко. Повторять, сколько не жалко времени.

Можете сюда опубликовать? Тоже интересно.

Много буков. Могу голосом надиктовать, а Вы сюда запишите. Ну или наберу в ТеХе, если будет завтра время лишнее.

Могу, конечно, псевдокод написать, но тогда ускользнет изящность идеи. А идея простая, я это первокурсникам рассказываю.

Поскольку в условиях задачи не указано, нужно ли стремиться к наиболее равномерному распределению длин отрезков по диапазону, то вот решение в лоб:

from random import choice

length = 1000
min_length = 1
max_length = 30
n = 120
list_of_lengths = []

sum_lengths = 0
while n > 0:
    n -= 1
    l = choice(xrange(min_length, max_length + 1))
    sum_lengths += l
    list_of_lengths.append(l)
    remainder = length - sum_lengths - (n - 1)
    if remainder < max_length:
        max_length = remainder

print list_of_lengths

А какое распределение случайной величины требуется?

возможных сумм 1000 не так уж много.

А очень и очень много.

С указанными ограничениями - совсем не много, особенно учитывая, что перестановки можно не считать.

Насколько я помню, полный набор разбиений для 1000 это >2 * 10**31. Можешь прикинуть, сколько будет с ограничениями?

Быстрый способ без каких-либо проверок внутри цикла: пусть A и B - это границы возможных отрезков, n - число отрезков, L - необходимая сумма длин всех отрезков. Находишь l=L/n - среднюю длину отрезков. Находишь p=min(l-A, B-l) - максимальное отклонение от среднего, которое ты можешь себе позволить с этим алгоритмом. Генерируешь отрезки парами, n-ая пара имеет длины l±p*0.95ⁿ. Константу подбираешь по вкусу, с нечётным количеством отрезков один отрезок остаётся длиной l.

Разбиваем на отрезки длиной l/N+e_i. Если l/N<=Mmin или l/N>=Mmax, то разбить нельзя. e_i = (i-N/2)*e, где е — очень малое число.

Всё, я решил твою задачу. Если это не то, что тебе было нужно, научись правильно формулировать условия.

Лучше бы упомянул дополнительные требования к набору из 120 отрезков. А то всегда можно:

L=1000м/120м=8.333(3)м

Требование, чтобы отрезки были неравными, озвучено. Так что не «всегда можно».

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

Вот и я о том же.

Требование, чтобы отрезки были неравными, озвучено. Так что не «всегда можно».

Ну, измени отрезки на небольшую, но различную для каждого отрезка, величину.

Если там ограничение, что «отрезки неравные», то, похоже, эта задача NP-полная, так как она является NP-задачей и плюс к ней сводится другая NP-полная задача о сумме подмножеств. Значит «быстрого» общего решения нет, используй любое подходящее частное.

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

Ну или просто генерацией: берешь N(120) отрезков по 1, оставшиеся L-N(880) метров распределяешь между отрезками случайным образом, пока отрезки <Nmax. Короче, вариантов меньше (L-N)^N / N! .

Если там ограничение, что «отрезки неравные», то, похоже, эта задача NP-полная, так как она является NP-задачей и плюс к ней сводится другая NP-полная задача о сумме подмножеств.

Не сводится.

У нас имеется диапазон действительных значений от 1 до 30 и количество элементов 120. Расширяем диапазон путём перехода от целых к десятичным, сотым, и так далее частям, до тех пор, пока количество полученных рациональных чисел не станет большим 120 (в данном случае достаточно перейти на десятые части). Умножаем искомую сумму (1000) на найденную разрядность (10 в данном случае).

В итоге имеем множество из 290 целых числ, подмножество из 120 целых чисел и целевое значение, равное 10000. Задача о сумме подмножеств, как она есть.

Привет. Допустим, есть дорога длиной 1 000 метров. Необходимо на ней поставить 120 остановок. Остановки должны быть на расстоянии друг от друга не менее 1 метра и не более 30.

Фикс под аватарку.

https://dumpz.org/2711242/

не благодари - за минуту сваял скрипт просто генерирующий случайные отрезки (и отсекающий уже встретившиеся варианты), за пять сек нашло уже больше 40к ариантов, с тебя 0.002 BTC за труды, братан

уже более 100к вариантов и находит так же быстро, полагаю все варианты перебрать нереально и это bigdata задачка для распределенного вычислеия

остановился на ~150k ариантах, не хочу машину повесить. короче здесь надо циклично обойти все варианты комбинаций в цикле цикла циклов вложенных вызовов рекурсий для более мелких условий (все отрезки от 1 до 2 метров, от 2 до 3, от 3 до 4) и потом еще найти все комбинации этих комбинаций. itertools в помащь

бля я там условие ко-ва отрезков провтыкал в спешке, патч:

        while sum(segments) < LENGTH and len(segments) < SIZE:
                segments.append(random.randrange(FROM, TO))
        if sum(segments) == LENGTH and len(segments) == SIZE:

хотя лучше уж для Ъ,

import os
import random
import json
import datetime

LENGTH = 1000
SIZE = 120

FROM = 1

TO = 30

found = []

while True:
	segments = []
	while sum(segments) < LENGTH and len(segments) < SIZE:
		segments.append(random.randrange(FROM, TO))
	if sum(segments) == LENGTH and len(segments) == SIZE:
		data = json.dumps(segments)
		if data not in found:
			print(datetime.datetime.now().strftime("%H:%M:%S"), segments[-5:])
			found.append(data)
			open("lines.json", "a").write(f"{data}{os.linesep}")

– тепрерь ничего не находит, более правдоподобно оч уж)

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

DER LINES 2.0

Итак, поняв что методом «рандомом в аллаха» ничего не найти, я собрался с мыслями и быстренько накатал новую версию скрипта.

DER LINES 0.2.0 использующая по-максимуму возможности стандартной библитотеки Писюнчика, вашему вниманию, короткая реализация:

import os
import datetime
import json
import itertools

DISTANCE = 1000
STEPS = 120
FROM = 1
TO = 30

variants = range(FROM, TO + 1)
combinations = itertools.combinations_with_replacement(
	variants, STEPS)
sequences = list(filter(lambda combination: sum(combination) == DISTANCE, combinations))
json.dump(sequences, "lines2.json")
print("Done.")

важно понимать, что все функции здесь возвращают генераторы (до момента вызова list(), а самих комбинаций невероятное количество и сколько даже посчитать я не дождался. потому сейчас перепешу в пошаговом императивном стиле вместо предикатов чтоб сделить за процессом, пока ниодного варианта нет

вообщем тут и добавить нечего, реализовал с пошаговым циклом - все работает, надо ждать пока найдет... оставлю наночь думать наверное

Очереджное оюновление (запилите ктота новость на гнолагне):

LICENSE: GPL-3 AUTHORS: ANONIME LEGIONY

import os ; import json ; import datetime ; now = datetime.datetime.now
import itertools ; import functools
time = lambda _ = None: (_ or now()).strftime("%H:%M:%S")
started_at = now()
DISTANCE = 1000 ; STEPS = 120 ; FROM = 1 ; TO = 30
print("DERLINES v0.3.5-compat", os.linesep, f"\b[RANGE({FROM}..{TO}) WHERE SUM(segments) IS {DISTANCE}]", os.linesep)
variants = filter(lambda _: sum(_) == DISTANCE,
	itertools.combinations_with_replacement(range(FROM, TO + 1), STEPS))
json.dump(list(variants), open("lines.log", "w"))
print(f"DONE({time(started_at)}–{time()})")

Небольшой ребрендинг и очередная версия, на этот раз в виде однострочника. Для чистоты эксперимента, это то что я оставлю бегать ночью:

from itertools import combinations_with_replacement as variants ; from json import dump ; dump(list(filter(lambda _: sum(_) is 1000, variants(range(1, 30 + 1), 120))), open("lines.log", "w"))

Кошель для донатов биткойнами сбрасывать?

У нас имеется диапазон действительных значений от 1 до 30 и количество элементов 120. Расширяем диапазон путём перехода от целых к десятичным, сотым, и так далее частям, до тех пор, пока количество полученных рациональных чисел не станет большим 120 (в данном случае достаточно перейти на десятые части). Умножаем искомую сумму (1000) на найденную разрядность (10 в данном случае).

Дичь какую-то пишешь, не распарсить.

Покажи на примере. Можно ли из {-2, -1, 4} получить 0? Сведи к задаче ТС.

Можно взять отрезок длины X, каждый следующий на Y длиннее. На X и Y есть ограничения:
120 * X + (120 + 1) * 120 / 2 * Y = 1000
X >= 1
X <= 30
Y > 0

С помощью линейного программирования выясняешь, не пусто ли множество решений. Оно не пусто. Выбираешь любую точку в множестве. Подходят, например, X = 1 и Y = 4/33.

кстати, за секунду на моем макпро (этого года) около 200 000 итераций пробегает и пока так ничего и не нашло, памяти кстати немного процесс занимает, всего 12мег, летает вообщем