Рекурсия строк в Rust

В Rust я пытаюсь получить все возможные комбинации символов az до фиксированной длины без повторяющихся букв.

Например, для ограниченного набора a-f и длины 3 я должен получить:

Азбука абд Абэ абф акб акд туз акф адб ... и т. д

Я изо всех сил пытался сделать это с помощью рекурсии и ударялся головой о владении и заимствованиях. Единственный способ, которым мне удалось это сделать, заключается в следующем, но это клонирование строк повсюду и очень неэффективно. Вероятно, в стандартной библиотеке для этого есть стандартные функции перестановки/комбинации, я не знаю, но мне интересно понять, как это можно сделать вручную.

fn main() {
    run(&String::new());
}

fn run(target: &String) {
    for a in 97..123 { // ASCII a..z
        if !target.contains(char::from(a)) {
            let next = target.clone() + char::from(a).to_string().as_str(); // Working but terrible
            if next.len() == 3 { // Required string size
                println!("{}", next);
            } else {
                run(&next);
            }
        }
    }
}

«вызвать другую функцию для этой строки, которая возвращает целое число» - подробности?

— 10.01.2023 19:11

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

— 10.01.2023 19:17

Давайте переместим часть «вызов другой функции» в другой вопрос. На StackOverflow принято задавать один вопрос на сообщение.

— 10.01.2023 19:18

ОК, отредактировано, чтобы удалить вторую часть вопроса.

— 10.01.2023 19:19

string recursion rust

10.01.2023 19:01

В чем разница между методом "==" и equals()

Это один из наиболее часто задаваемых вопросов новичкам на собеседовании. Давайте обсудим его на примере.

Замена символа по определенному индексу в JavaScript

В JavaScript существует несколько способов заменить символ в строке по определенному индексу.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Прежде всего, пара замечаний:

&String — это своего рода анти-паттерн, который редко встречается. Это бесполезно; вся функциональность, которую String имеет по сравнению с str, требует изменчивости. Так что это должно быть либо &mut String, либо &str.
97..123 редко... используйте 'a'..='z'.

Теперь к самой проблеме:

Пока вы передаете неизменяемую строку в рекурсию, вы не сможете обойти клонирование данных. Я бы сделал строку изменяемой, тогда вы можете просто добавлять и удалять из нее отдельные символы.

Так:

fn main() {
    run(&mut String::new());
}

fn run(target: &mut String) {
    for a in 'a'..='z' {
        if !target.contains(a) {
            target.push(a);
            if target.len() == 3 {
                // Required string size
                println!("{}", target);
            } else {
                run(target);
            }
            target.pop();
        }
    }
}

Спасибо. Я пробовал этот подход раньше, но поставил target.pop() не в том месте :) Спасибо и за полезные замечания. Должен ли я опубликовать еще один вопрос об обработке возвратов при передаче target в другую функцию со ссылкой на этот пост?

— 10.01.2023 19:29

Просто откройте новый вопрос с описанием проблемы, что вы пробовали и почему у вас возникли проблемы.

— 10.01.2023 19:29

— 10.01.2023 19:45

Поскольку выполнение всех перестановок для 7-буквенной строки является очень долгим процессом, мне интересно, есть ли способ запустить процесс рекурсии с помощью строки «начало». Через 20 минут (один поток) с компиляцией выпуска я получаю результаты для строки abelrst (все еще начинающейся с «a»). Есть ли способ указать эту строку в качестве начального значения, если машина выйдет из строя?

— 10.01.2023 20:35

Способов много, хотя все они не по теме данного вопроса. Попробуйте реализовать это самостоятельно, и если вы столкнетесь с конкретной проблемой, с которой не знаете, как справиться, откройте новый вопрос, описывающий ее, то, что вы пробовали, и почему вы боретесь :) Научиться решать проблемы - это №1 самый важный навык для программиста, все остальное, например, языки и механизмы, менее важны. Поэтому я всегда призываю хорошенько разобраться в проблеме, прежде чем просить о помощи.

— 10.01.2023 20:42

Я согласен, именно поэтому я пытался решить эту проблему рекурсии, не полагаясь на внешние ящики. Это просто самодельная, совершенно не профессиональная головоломка. Передача начальной строки в цикл a..z for казалась безумной идеей, но я попробую. Спасибо за вашу поддержку.

— 10.01.2023 21:38

Не супер сумасшедший, но и не прямой. Удачи :) Одной из идей было бы проверить, будет ли последний элемент текущей run функции еще до контрольной точки, и если да, то вернуться из функции. Это должно перейти к контрольной точке всего за пару итераций.

— 10.01.2023 22:25

10.01.2023 19:17

Просто для полноты, вот альтернативный способ сделать это, когда не используется рекурсия. Он использует .permutations() из ящика Itertools.

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

use std::ops::RangeInclusive;
use itertools::Itertools;

fn main() {
    println!("result: {}",combine('a'..='d', 3));
    println!("result: {}",combine('a'..='g', 4));
    println!("result: {}",combine('a'..='c', 3));
    println!("result: {}",combine('a'..='c', 4)); // assertion fail
}

fn combine(range: RangeInclusive<char>, depth: usize) -> String
{
    assert!( *range.end() as usize - *range.start() as usize + 1 >= depth);

    let perms = range.permutations(depth);
    let mut result = String::new();

    perms.for_each(|mut item| {
        item.push(' ');
        result += &item.into_iter().collect::<String>();
    });
    result.pop(); // pop last superfluous space char
    result
}

Хотя это хорошее решение imo, OP явно просил решения без .permutations().

— 11.01.2023 00:21

@Finomnis, мой плохой, я пропустил эту часть вопроса. немного отредактировал ответ.

— 11.01.2023 07:59

10.01.2023 20:18