Перетасовка Фишера-Йейтса на одной строке по сравнению с использованием перестановки равной длины?

Прямо сейчас я работаю над набором словесных игр в качестве средства самообучения (и воссоздаю некоторые из моих любимых словесных игр!) С помощью «настоящего» друга-программиста мы реализовали хороший метод перестановки в мои занятия. Он находит все перестановки от 3 букв и выше и сравнивает их со списками строк, которые у меня есть, содержащими то, что по сути является списком слов турнира Scrabble.

Это предыстория, вот моя текущая проблема: теперь у меня есть все перестановки, я сравнил их с существующими словами и создал новый список со всеми возможными комбинациями слов в данной строке. Однако, когда я представляю эту строку пользователю, мне нужно, чтобы она была зашифрована. Я нашел несколько реализаций перетасовки Фишера-Йейтса на С#, но мне не удалось адаптировать их для приема одной строки (EDIT: проблема Фишера-Йейтса решена с помощью массива char[]). Затем у меня появилась идея для небольшого хака - почему бы не использовать одну из перестановок той же длины, но != оригинальное слово.

К сожалению, каждый раз мой условный оператор возвращает слово задом наперед. Конечному пользователю не так сложно это понять :) Вот мой код для скремблирования:

// permWords is a Dictionary<int, List<string>>
String strScrambled= "";

        foreach (List<string> listWords in permWords.Values)
        {
            foreach (string word in listWords)
            {
                if (word.Length == strWord.Length && word != strWord)
                {
                    strScrambled = word;
                }

            }
        }

Я пробовал strScrambled = word + 1, предполагая, что первая перестановка, неравная оригиналу, была словом назад. Однако я не думаю, что это действительно «работает» в данном контексте; особенно учитывая, что он по-прежнему возвращает одно и то же слово в обратном порядке.

Был дан очень полезный ответ о том, как решить мою проблему с Фишером-Йейтсом с помощью массива символов, но мне все еще очень любопытно узнать, как лучше всего использовать что-то вроде того, что я опубликовал, только найдя способ убедиться, что ответ — это не просто слово, написанное наоборот. Я заинтригован этим методом, потому что список перестановок уже существует; Я хотел бы использовать это как свое решение.


c# shuffle permutation
person armadadrive    schedule 28.11.2012    source источник
comment
возможный дубликат Перемешать строку c#   -  person mbeckish    schedule 28.11.2012
comment
Почему бы вам не преобразовать строку в char[] с помощью st.ToCharArray(), перетасовать ее так, как вам нравится, а затем преобразовать обратно в строку с помощью arr.ToString()?   -  person Ali Ferhat    schedule 28.11.2012
comment
Ааа, массив символов! Это отличная идея. Напиши это как ответ, и я отдам тебе должное, @AliFerhat.   -  person armadadrive    schedule 28.11.2012
comment
@mbeckish Возможно, если этот пост содержит информацию о работе со списком перестановок строки. Я не пытаюсь быть легкомысленным, но я четко обозначил два сценария, которые я изучаю, чтобы попытаться решить свою проблему, и я хотел бы получить лучший совет, который я могу получить, чтобы учиться и двигаться вперед.   -  person armadadrive    schedule 28.11.2012
comment
@armadadrive - Только один из ваших описанных сценариев требует работы со списком перестановок. Первое решение просто требует, чтобы вы перетасовывали по одной строке за раз, верно?   -  person mbeckish    schedule 28.11.2012
comment
@mbeckish Один из двух способов сделать это, которые я описал, - перетасовать строку. Однако мне не интересно спорить о достоинствах вопроса; Теперь мне интересно узнать, как лучше всего решить мою проблему со списком перестановок, потому что некоторые полезные советы также были даны с проблемой, с которой я столкнулся в отношении перетасовки строк.   -  person armadadrive    schedule 28.11.2012

Ответы (2)


arrow_upward
3
arrow_downward

Я полагаю, у вас уже есть метод, который выполняет перетасовку:

void FisherYatesShuffle(char[] elements)
{
    int N = elements.Count;
    for(int i = 0; i<N-1; i++)
    {
        // exchange elements[i] with a random element in i+1 .. N
    }   
}

Все, что вам нужно сделать, это преобразовать вашу строку в CharArray, а затем преобразовать результат обратно в строку:

string shuffle(string input)
{
    var arr = input.ToCharArray();
    FisherYatesShuffle(arr);
    return new String(arr);
}
person Ali Ferhat    schedule 28.11.2012
comment
Спасибо. Дайте мне знать, если у вас есть какие-либо мысли о том, как лучше всего использовать одну из моих случайных перестановок в качестве альтернативного решения. Как я упоминал в посте, первое условие, которое всегда оценивается как истинное, — это перестановка, в которой строка находится в обратном порядке. Я чувствую, что это также может быть полезным способом «зашифровать», потому что все перестановки уже существуют в List. - person armadadrive; 28.11.2012

arrow_upward
1
arrow_downward

Посмотрите, сработает ли это для вас...

string str = "hello";

// The random number sequence
Random num = new Random();

string rand = str;
while (rand == str)
    rand = new string(str.OrderBy(s => (num.Next())).ToArray());

Если вы хотите убедиться, что перетасованное значение не является точным обратным, вы можете изменить условие while на...

while (rand == str || rand == str.Reverse())
person Gene S    schedule 28.11.2012
comment
Спасибо, это работает отлично. Все, что мне нужно сделать, это присвоить значение rand для strScrambled. - person armadadrive; 28.11.2012
comment
ОП начинает с попытки использовать эффективный и действенный алгоритм перетасовки, а вместо этого вы используете менее эффективную и менее эффективную альтернативу? - person Servy; 28.11.2012
comment
Сортировка обычно менее эффективна, чем генерация случайной перестановки. - person Ali Ferhat; 28.11.2012
comment
@Servy Хотя то, что вы говорите, правда, он указал в своем вопросе, что любое предложение будет помощью. Я просто пытался предложить альтернативу, которая будет делать то, что он просил. Из его вопроса я не понял, что использование Фишера-Йейтса было требованием, просто это был подход, который он пытался использовать. - person Gene S; 28.11.2012
comment
@GeneS Это шаг назад. Он использует менее эффективный подход более высокого уровня вместо того, чтобы решать проблемы, которые у него были, в правильном подходе. Кстати, проблема с его подходом, вероятно, в том, что ему нужно было преобразовать строку в массив символов, перетасовать ее, а затем преобразовать обратно в строку. Вы все это сделали, только не объяснили, что это то, что вы исправили. Вы могли бы сделать это, не возвращаясь к более бедному методу перетасовки, и это был бы отличный ответ. - person Servy; 28.11.2012
comment
Хотя ответ не так хорош, как другой, я не думаю, что он заслуживает отрицательной оценки. - person redtuna; 09.04.2013