Алгоритм генерации всех комбинаций строки

Question

Я нашел онлайн ссылку, которая показывает алгоритм для генерации всех комбинаций строки: http://www.mytechinterviews.com/combinations-of-a-string

Алгоритм скопирован ниже.

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

Что я не понимаю, так это строка:

outstr.deleteCharAt(outstr.length() - 1);

Если я уберу эту строку, программа, очевидно, больше не будет работать, но зачем это нужно в первую очередь? Я понимаю рекурсивную идею, в которой мы меняем начальный символ и рекурсируем оставшиеся символы, но строка deleteChar, похоже, никуда не вписывается. Какова была причина добавления строки outstr.deleteCharAt?

Answer 1

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

Математически найти R комбинаций в заданной партии N = NcR

Итак, мы находим здесь:все возможные комбинации = Nc0 + Nc1 .... + Ncn = 2 Pow N

Таким образом, вы получаете 2 комбинации Pow N для заданного слова длиной N символов.

Если вы представляете от 1 до (2 Pow N) целые числа в двоичном виде, и поместите свой символ в место, где присутствует 1, наконец, вы получите решение.

Пример:

Ввод: ABC

Решение:

Длина ABC равна 3. Таким образом, возможные комбинации 2 Pow 3 = 8

Если 0 - 8 представлены в двоичном виде

000 =

001 =C

010 = B

011 = BC

100 = A

101 = AC

110 = AB

111 = ABC

все возможные комбинации показаны выше.

Answer 2

Вызов outstr.deleteCharAt противодействует эффекту outstr.append, удалив последний символ outstr.

Каждая итерация цикла выполняется следующим образом:

1. добавить символ
2. распечатать результат
3. выполнить рекурсивный вызов на уровне i+1
4. удалить символ, который мы добавили на шаге 1

Answer 3

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

Answer 4

Ниже приведен код для генерации перестановки и комбинации строк, в основном концепция заключается в выборе одного символа за раз:

public class permutecombo
{
  static void initiate(String s)
  {
    permute("", s);
    System.out.println("----------------------------------------- ");
    combo("", s);
    System.out.println("----------------------------------------- ");
  }

  static void combo(String prefix, String s)
  {
    int N = s.length();

    System.out.println(prefix);

    for (int i = 0 ; i < N ; i++)
      combo(prefix + s.charAt(i), s.substring(i+1));
  }
  static void permute(String prefix, String s)
  {
    int N = s.length();

    if (N == 0)
      System.out.println(" " + prefix);

    for (int i = 0 ; i < N ; i++)
      permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
  }

  public static void main(String[] args)
  {
    String s = "1234";
    initiate(s);
  }
}

Answer 5

Подходит очень логично.Вы видите, что у нас здесь есть рекурсивный алгоритм.На каждом шаге в позиции i мы помещаем букву строки, а затем рекурсивно вызываем функцию, чтобы поместить следующую букву в следующую позицию.Однако, когда мы возвращаемся из рекурсии, нам нужно удалить символ, который мы изначально поместили, чтобы мы могли заменить его следующим возможным в последовательности.Пример:

append a on pos 0 -> a
call recursion
append a on pos 1 -> aa
call recursion
append a on pos 2 -> aaa
return from recursion
remove a from pos 2 -> aa
append b on pos 2 -> aab
return from recursion
remove b from pos 2 -> aa
append c on pos 2 -> aac
etc.

Answer 6

Мы можем генерировать все подстроки строки, используя концепцию битов, которая была упомянута ранее.Вот код (на C ++, но у вас есть идея) для этого: -

string s;
int n = s.size();
int num = 1<<n;
for(int i =1; i< num ; i++){ //Checks all the permutations.
    int value = i;
    int j, pos;
    for (j=1, pos=1; j < num; j<<=1, pos++) //Finds the bits that are set
        if (i & j)
            cout<<s[pos-1]; //You can print s[n-pos] to print according to bit position
    cout<<endl;        
}

Например; - Строка s = abc ,

 The size is 3  . So we check from 1 to 7 ( 1<<3).
 for i = 1 ( 001 ) , the first bit is set, so a is printed.
 for i = 2 ( 010 ) , the second bit is set, so b is printed.
 for i = 3 ( 011 ) , the first and second bit are set, so ab is printed.
 .
 .
 .
 for i = 7 ( 111 ) , all three bits are set, so abc is printed.

Answer 7

Вот код C ++ без хитрого возврата в вопросе OP.

#include <iostream>
#include <string>
using namespace std;
static const string in("abc");
void combine(int i, string out)
{
    if (i==in.size()) {
        cout << out << endl;
        return;
    }
    combine(i+1, out);
    combine(i+1, out+in[i]);
}

int main()
{
    combine(0, "");
    return 0;
}

Надеюсь, это лучше отражает дух комбинаций.

Answer 8

outstr.deleteCharAt(outstr.length() - 1); 

означает, что у вас есть

n^(n-1)/2 pairs of combinations.

Итеративный цикл for не останавливается после вызова рекурсивной функции, поэтому вам нужно удалить последний символ в буфере вывода, потому что вы этого не сделаетехочу получить

n^n/2 pairs of combinations.

В теории графов это будет короткое замыкание.

Answer 9

// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

import java.util.*;
public class Permutation {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("ENTER A STRING");
        Set<String> se=find(in.nextLine());
        System.out.println((se));
    }
    public static Set<String> find(String s)
    {
        Set<String> ss=new HashSet<String>();
        if(s==null)
        {
            return null;
        }
        if(s.length()==0)
        {
            ss.add("");
        }
        else
        {
            char c=s.charAt(0);
            String st=s.substring(1);
            Set<String> qq=find(st);
            for(String str:qq)
            {
                for(int i=0;i<=str.length();i++)
                {
                    ss.add(comb(str,c,i));
                }
            }
        }
        return ss;

    }
    public static String comb(String s,char c,int i)
    {
        String start=s.substring(0,i);
        String end=s.substring(i);
        return start+c+end;
    }

}


// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!