Как я могу генерировать целые числа, которые удовлетворяют некоторым ограничениям?

Question

Может ли кто-нибудь помочь мне с методами получения целых чисел, которые удовлетворяют определенным ограничениям.

Например, скажем, мне нужно сгенерировать целые числа x и y так, чтобы

      100 > x
and   y < x + 5

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

Answer 1

Ну, это не так сложно:

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

Если у вас несколько целых чисел, таких как x и y в вашем примере, замените "целое число" на "целые числа".

Этот метод также известен как выборка отклонения .

Вы можете реализовать это, например, с помощью серии цепочек итераторов. И некоторые ограничения работают довольно хорошо в качестве генераторов, например, «положительные целые числа меньше 100», так что вы, вероятно, начнете с одного из них, прежде чем отфильтровать все остальные ограничения.

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

Answer 2

Если все ваши ограничения могут быть записаны как набор линейных уравнений, вы можете использовать линейное программирование , чтобы найти решение для максимизации 'c1 * x + c2 * y'. Для c1 и c2 вы можете нарисовать случайные значения. Особенно, если у вас много ограничений и переменных, которые могут быть быстрее, чем просто пробовать случайные значения для x и y.

Answer 3

Эта проблема - то, для чего была разработана Prolog . Вы также можете посмотреть на новые языки, такие как Моцарт для более современного взгляда. Декларативная модель программирования должна объявлять ограничения для ваших выходных данных, а затем получать ответы, которые удовлетворяют указанным ограничениям.

Цитировать страницу Википедии для Пролога:

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

Answer 4

Вы хотите взглянуть на языки на основе ограничений. Например, CLIP позволит вам указать ваши ограничения, а затем вернет набор интервалов, которые удовлетворяют всем вашим ограничениям.

Answer 5

Если это язык сценариев, вы можете передать минимальные и максимальные значения x и y и массив тестов в функцию, а затем использовать rand для генерации начальных значений в вашем диапазоне.

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

Это было бы универсальным решением вашей проблемы.

Answer 6

Если вы чувствуете себя LINQ-y, вы можете начать со Списка всех возможных пар x, y, а затем применить условие where для каждого условия. Из всего, что осталось, вы можете выбирать предметы случайно.

Dim everything As List(Of Point) = generate_pairs()
Dim rest As List(Of Point) = everything.Where(Function(pp) pp.X > 100).ToList
rest = rest.Where(Function(pp) pp.Y < pp.X + 5).ToList
Dim rnd As New Random()
Dim r As Integer = rnd.Next(rest.Count)
Dim p As Point = rest.Skip(r).Take(1).SingleOrDefault
System.Console.WriteLine("x: " & p.X & " y: " & p.Y)