C # Поиск "связанных" перестановок

Question

Я работаю над таблицей словаря и должен выяснить все возможные комбинации символов в слове.Благодаря https://codereview.stackexchange.com/questions/28248/implement-a-function-that-prints-all-possible-combinations-of-the-characters-in я до сих пор работал ниже:

    public List<string> findAllOccurance(string str)
    {
        var results = from e in Range(0, BigInteger.Pow(2, str.Length))
             let p =
                 from b in Enumerable.Range(1, str.Length)
                 select (e & BigInteger.Pow(2, b - 1)) == 0 ? (char?)null : str[b - 1]
             select string.Join(string.Empty, p);

        return results.ToList();
    }

    public IEnumerable<BigInteger> Range(BigInteger start, BigInteger count)
    {
        while (count-- > 0)
        {
            yield return start++;
        }
    }

Передача "abc" в вышеприведенную функцию вернула бы:

a
b
ab
c
ac
bc
abc

Проблема в том, что я на самом делехотел бы узнать только «связанные» перестановки в «исходном порядке», например, «abc» должен возвращать только

a
b
c
ab
bc
abc

Кто-нибудь знает, что я должен изменить, чтобы достичь выше?

Answer 1

Путем «связанных» перестановок - вы фактически ищете все подстроки от длины 1 до полной длины строки. Это можно легко сделать с помощью двух циклов for. Дубликаты могут быть удалены с помощью метода Linq Distinct ().

public List<string> findAllOccurance(string str)
{
    List<string> result = new List<string>();
    for (int i = 1; i <= str.Length; i++)
    {
      for (int j=0; j <= str.Length-i; j++)
        result.Add(str.Substring(j,i));
    }
    return result.Distinct().ToList();
}

ПРИМЕЧАНИЕ. Если вы действительно хотите вернуть пустую строку, вы можете либо изменить внешний цикл, чтобы он начинался с 0, либо просто добавить его вручную после создания экземпляра списка. Изменение цикла приведет к добавлению пустых строк str.Length и дополнительной работы для Distinct (), когда вы знаете, что всегда будете хотеть, чтобы возвращалась только 1 пустая строка.

List<string> result = new List<string>();
result.Add(String.Empty);
for (int i = 1; i <= str.Length; i++)
.....

Answer 2

Для вашего кода вы выполняете побитовую операцию, чтобы найти все возможные подмножества.Для случая abc ваша длина строки равна 3. Таким образом, возможные подмножества = 2 ^ 3 = 8. Записать их и сопоставить самый правый бит с крайним левым индексом:

Possible cases: 
0 0 0     // gives nothing
0 0 1     // gives 'a' (valid)
0 1 0     // gives 'b' (valid)
0 1 1     // gives 'ab' (valid)
1 0 0     // gives 'c' (valid)
1 0 1     // gives 'ac' (invalid as there is a 0 inbetween and not connected)
1 1 0     // gives 'bc' (valid)
1 1 1     // gives 'abc' (valid)

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

int max_size = BigInteger.Pow(2, str.Length);
int str_size = str.Length;
for(int i = 0; i < max_size; ++i) 
{ 
    string ans = "";
    for(j = 0; j < str_size; ++j) 
   { 
      // We check if the jth bit is set, we print the jth element from the string.
       if(i & (1 << j)) 
           ans += str[j];
       } 
       else {
           if(ans.Length > 0){
               // this means we have already added a character and then the next consecutive bit is '0'
               ans = "";
               break;
           }
       }
      if(ans != ""){
           Console.Writeline(ans); // we print the set. you can control this anyway you want.
      } 
   }   
} 

Answer 3

Не знаю, правильно ли я понимаю «подключен» ... Может быть, вы могли бы просто проверить, является ли потенциальный результат частью исходной строки ... Примерно так:

public List<string> findAllOccurance(string str)
{
    var results = from e in Range(0, BigInteger.Pow(2, str.Length))
         let p =
             from b in Enumerable.Range(1, str.Length)
             select (e & BigInteger.Pow(2, b - 1)) == 0 ? (char?)null : str[b - 1]
         let p2 = string.Join(string.Empty, p)
         where str.Contains(p2)
         select p2;

    return results.ToList();
}

public IEnumerable<BigInteger> Range(BigInteger start, BigInteger count)
{
    while (count-- > 0)
    {
        yield return start++;
    }
}