1

Я совсем новичок, поэтому скорее всего изъяснился неверно.

  • Есть массив: {1,3,4,5,6,7,9}, необходимо сгруппировать из него коллекцию чисел заданным числом символов n.
  • Если n=1, то последовательность будет: 1,3,4,5,6,7,9.
  • Если n=2, то последовательность будет: 11,13,14,15,16,17,19,31,33,34...99.

И т.д.

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

Вроде появилась заявка на победу:

import java.util.Scanner;

public class Main {
    private static void permutation(String prefix, String str, int n) {

        if (n == 0) System.out.println(prefix);
        else {
            for (char elem: str.toCharArray()) {
                permutation(prefix + elem, str, n-1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str = sc.next();
        permutation("", str, n);
    }
}
2
  • Генерация всех кортежей заданной длины.
    – Harry
    12 авг 2019 в 14:42
  • 1
    В рамках комбинаторики это перестановки (размещения) с повторениями 12 авг 2019 в 14:48

3 ответа 3

1

Генерация всех кортежей заданной длины.

Д. Кнут, Искусство программирования, т. 4А, раздел 7.2.1.1 - "Генерация всех n-кортежей".

Если укажете задание более конкретно - ну, например, фиксировано ли n при компиляции или произвольно, какой используется язык программирования, в каком виде представлены данные - можно будет и поговорить подробнене :)

1
  • Добавил вариант неверного решения в топик на Java.
    – Lex
    12 авг 2019 в 15:31
1

В рамках комбинаторики это называется перестановки (размещения) с повторениями.

Алгоритмически, можно воспользоваться тем, что имея некую перестановку (число в вашем случае) длины n, перестановки длины (n+1) можно получить из нее просто в цикле поочередно добавляя тот или иной элемент:

процедура ВыводПерестановок(ТекущаяПерестановка, Множество, ДлинаПерестановки)
  если ДлинаПерестановки == 0:
    вывод ТекущаяПерестановка
    возврат
  для всех Элемент из Множество:
    ВыводПерестановок(ТекущаяПерестановка + Элемент, Множество, ДлинаПерестановки - 1)

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

4
  • Добавил в топик вариант в Java, половина подстановок теряется. Что я упустил?
    – Lex
    12 авг 2019 в 15:30
  • @Lex, вы не дословно перевели мой псевдокод в Java, я множество никак не изменяю при передаче рекурсивно, передавать нужно именно исходное множество, ничего из него не отбрасывая. 12 авг 2019 в 15:32
  • т.е. передавайте прямо str, а не str.substring(0, i) + str.substring(i+1, n) 12 авг 2019 в 15:33
  • Доработал, есть ли в моём коде вопиющие глупости? Что можно оптимизировать?
    – Lex
    12 авг 2019 в 15:49
1

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

public static void main (String[] args) throws java.lang.Exception
{
    String str = "1357";
    int L = str.length();
    int N = 3;
    int pow = 1;
    for (int i = 0; i < N; i++) 
        pow *= L;  // L^N
    for (int i = 0; i < pow; i++) 
    {
        int tmp = i;
        String res = "";
        for (int k = 0; k < N; k++)
        {
            res = str.charAt(tmp % L) + res;         //integer modulo
            tmp = tmp / L;      
        }
        System.out.println(res);
    }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.