Перестановки капитализации - PullRequest
Новая
       48

Перестановки капитализации

3 голосов
/ 25 мая 2009

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

List<string> permutate(string word)
{
    List<string> ret = new List<string>();
    MAGIC HAPPENS HERE
    return ret;
}

Скажем, я вставил "happy" Я должен получить массив обратно 

{happy, Happy, hAppy, HAppy, haPpy, HaPpy ... haPPY, HaPPY, hAPPY, HAPPY}

Я знаю множество функций, которые будут использовать заглавные буквы первой буквы, но как мне сделать любую произвольную букву в слове?

Ответы [ 8 ]

8 голосов
/ 25 мая 2009

Вы можете изменить отдельные символы, если вы преобразуете свою строку в массив char. Нечто подобное должно сработать ... 

public static List<string> Permute( string s )
{
  List<string> listPermutations = new List<string>();

  char[] array = s.ToLower().ToCharArray();
  int iterations = (1 << array.Length) - 1;

  for( int i = 0; i <= iterations; i++ )
  {
    for( int j = 0; j < array.Length; j++ )
    array[j] = (i & (1<<j)) != 0 
                  ? char.ToUpper( array[j] ) 
                  : char.ToLower( array[j] );
    listPermutations.Add( new string( array ) );
  }
  return listPermutations;
}
1 голос
/ 25 октября 2018

Мне удалось создать консольное приложение, которое делает это .. 

 public static class Program
{
    static void Main()
    {
        Console.WriteLine("Enter string");
        string value = Console.ReadLine();

        value = value.ToLower();

        List<string> list = new List<string>();

         var results =
             from e in Enumerable.Range(0, 1 << value.Length)
             let p =
             from b in Enumerable.Range(0, value.Length)
             select (e & (1 << b)) == 0 ? (char?)null : value[b]
             select string.Join(string.Empty, p);

        foreach (string s in results)
        {
            string newValue = value;
            s.ToLower();
            foreach(char c in s)
            {
                var Old = c.ToString().ToLower();
                var New = c.ToString().ToUpper();
                newValue=ReplaceFirstOccurrence(newValue, Old, New);
            }
            list.Add(newValue);
        }

        foreach(string s in list)
        {
            Console.WriteLine(s);
        }

        Console.ReadKey();
    }

    public static string ReplaceFirstOccurrence(string Source, string Find, string Replace)
    {
        int Place = Source.IndexOf(Find);
        string result = Source.Remove(Place, Find.Length).Insert(Place, Replace);
        return result;
    }    
}

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

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

1 голос
/ 25 мая 2009

Чтобы «переставить» вашу строку (технически это не перестановка, поскольку вы ничего не меняете, но я не хочу, чтобы вас воспринимали как * l-retentive :-) используйте рекурсивный подход, который в основном «переставляет» строку минус первый символ и присоединяет их к верхней и нижней вариациям этого символа.

Что-то вроде (в C мой C # на самом деле не на высоте, поэтому вам придется его преобразовать): 

#include <stdio.h>
#include <string.h>

static void permute (char *prefix, char *str) {
    char *newPrefix;

    /* End of string, print and return. */

    if (*str == '\0') {
        printf ("%s\n", prefix);
        return;
    }

    /* Allocate space for new prefix. */

    if ((newPrefix = malloc (strlen (prefix) + 2)) == NULL) {
        printf ("ERROR: Cannot allocate memory.\n");
        return;
    }

    /* Do lowercase/sole version and upper version if needed. */

    sprintf (newPrefix, "%s%c", prefix, *str);
    permute (newPrefix, &(str[1]));

    if (islower (*str) {
        sprintf (newPrefix, "%s%c", prefix, toupper(*str));
        permute (newPrefix, &(str[1]));
    }

    /* Free prefix and return. */

    free (newPrefix);
}


int main (int argc, char *argv[]) {
    char *str, *strPtr;

    /* Check and get arguments. */

    if (argc < 2) {
        printf ("Usage: permute <string to permute>\n");
        return 1;
    }

    if ((str = malloc (strlen (argv[1]) + 1)) == NULL) {
        printf ("ERROR: Cannot allocate memory.\n");
        return 1;
    }
    strcpy (str, argv[1]);

    /* Convert to lowercase. */
    for (strPtr = s; *strPtr != '\0'; strPtr++)
        *strPtr = toupper (*strPtr);

    /* Start recursion with empty prefix. */

    permute ("", str);

    /* Free and exit. */

    free (str);
    return 0;
}

Выполнение этого как "permute Pax1" возвращает: 

pax1
paX1
pAx1
pAX1
Pax1
PaX1
PAx1
PAX1
1 голос
/ 25 мая 2009

Имейте в виду, что, хотя принятый ответ является наиболее простым способом использования заглавных букв в произвольной форме, если вы собираетесь многократно менять заглавные буквы на одном и том же наборе букв (например, 32 раза в «счастливом» и расти в геометрической прогрессии для более длинные слова), будет более эффективно превратить строку в символ [], установить соответствующую букву (буквы) и создать строку из массива.

0 голосов
/ 21 июня 2019

Если заказ не имеет значения, вы можете попробовать Linq . Мы перечисляем все двоичные числа в диапазоне [0..2**word.Length]. и обрабатывать каждое число как mask : 0 - строчные буквы, 1 - прописные FDor экземпляр для happy у нас есть 

mask      string
----------------
00000  ->  happy
00001      Happy
00010      hAppy
00011      HAppy
00100      haPpy
00101      HaPpy
...
11111      HAPPY

Код: 

  using System.Linq;

  ... 

  List<string> permutate(string word) =>
    Enumerable
      .Range(0, 1 << word.Length)
      .Select(mask => string.Concat(word.Select((c, i) => (mask & (1 << i)) == 0 
         ? char.ToLower(c) 
         : char.ToUpper(c))))
      .ToList();

Демо-версия: 

  Console.Write(string.Join(", ", permutate("happy")));

Результат: 

happy, Happy, hAppy, HAppy, haPpy, HaPpy, hAPpy, HAPpy, hapPy, HapPy, hApPy, HApPy, haPPy, HaPPy, hAPPy, HAPPy, happY, HappY, hAppY, HAppY, haPpY, HaPpY, hAPpY, HAPpY, hapPY, HapPY, hApPY, HApPY, haPPY, HaPPY, hAPPY, HAPPY
0 голосов
/ 25 мая 2009

Предполагая, что:

1) Тебя не слишком волнует, что это O (n * 2 ^ n) ... хотя мне любопытно узнать: каково лучшее время асимптотики для этого типа проблемы?

2) Ваш ввод строчных букв.

3) Ваш ввод <32 символа. (число используемых бит в счетчике перестановок, i) </p> 

    List<string> permutate(string word)
{
    List<string> ret = new List<string>();

// MAGIC HAPPENS HERE
Dictionary<char,char> toUppers = new Dictionary<char,char>(26);
toUppers.Add('a', 'A');
toUppers.Add('b', 'B');
toUppers.Add('c', 'C');
toUppers.Add('d', 'D');
toUppers.Add('e', 'E');
toUppers.Add('f', 'F');
toUppers.Add('g', 'G');
toUppers.Add('h', 'H');
toUppers.Add('i', 'I');
toUppers.Add('j', 'J');
toUppers.Add('k', 'K');
toUppers.Add('l', 'L');
toUppers.Add('m', 'M');
toUppers.Add('n', 'N');
toUppers.Add('o', 'O');
toUppers.Add('p', 'P');
toUppers.Add('q', 'Q');
toUppers.Add('r', 'R');
toUppers.Add('s', 'S');
toUppers.Add('t', 'T');
toUppers.Add('u', 'U');
toUppers.Add('v', 'V');
toUppers.Add('w', 'W');
toUppers.Add('x', 'X');
toUppers.Add('y', 'Y');
toUppers.Add('z', 'Z');

char[] wordChars = word.ToCharArray();
int len = wordChars.Length;

// iterate the number of permutations
for(int i = 0; i < 2^len; i++) {
    char[] newWord = new char[len]();

    // apply "i" as a bitmask to each original char
    for(int n = 0; n < newWord.Length; n++) {
        if((1 << n) & i != 0) {
            newWord[n] = toUppers[wordChars[n]]; // or skip the dictionary and just call Char.ToUpper(wordChars[n])
        } else {
            newWord[n] = wordChars[n];
        }
    }
    ret.Add(new String(newWord));
}

    return ret;
}

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

0 голосов
/ 25 мая 2009

Использовать побитовые операции. Для слова длиной N вам нужен целочисленный тип, представленный N битами. Если слово длиннее - разделите его. Переберите значения от 0 до 2 N -1 и проверьте каждый бит от 0 до N-1. Если бит равен 1 - в верхнем регистре (Char.ToUpper()) буква, соответствующая этому биту.

Этот подход лучше рекурсивного алгоритма, поскольку он не склонен к переполнению стека длинных слов.

0 голосов
/ 25 мая 2009

Грубо говоря, что-то вроде ниже. Возможно, мои диапазоны отключены на единицу, но идея звучит здраво. 

def cap_n(in_str, pos):
  leading = in_str.substr(0, pos-1)
  trailing = in_str.substr(pos+1) # no second arg implies to end of string
  chr = in_str[pos].to_uppercase()
  return leading + chr + trailing
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...