Как получить все комбинации последовательностей строки (в Java или C ++ и т. Д.)

Question

Допустим, у меня есть строка "12345". Я должен получить все последовательности этой последовательности, такие как:

1. -> 1 2 3 4 5
2. -> 12 13 14 15 23 24 25 34 35 45
3. -> 123 124 125 234 235 345
4. -> 1234 1235 1245 1345 2345
5. -> 12345

Обратите внимание, что я сгруппировал их по разному количеству символов, но не изменил их порядок. Мне нужен метод / функция, которая делает это.

Answer 1

Вы хотите powerset. Вот все вопросы о StackOverflow, которые упоминают powersets или powersets .

Вот базовая реализация на python:

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield [s[j] for j in range(n) if (masks[j] & i)]


if __name__ == '__main__':
    for elem in powerset([1,2,3,4,5]):
        print elem

А вот его вывод:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]
[5]
[1, 5]
[2, 5]
[1, 2, 5]
[3, 5]
[1, 3, 5]
[2, 3, 5]
[1, 2, 3, 5]
[4, 5]
[1, 4, 5]
[2, 4, 5]
[1, 2, 4, 5]
[3, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]

Обратите внимание, что его первым результатом является пустой набор. Измените итерацию с for i in xrange(2**n): на for i in xrange(1, 2**n):, если вы хотите пропустить пустой набор.

Вот код, адаптированный для вывода строки:

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield "".join([str(s[j]) for j in range(n) if (masks[j] & i)])

---

Редактировать 2009-10-24

Хорошо, я вижу, что вы неравнодушны к реализации на Java. Я не знаю Java, поэтому я встречу вас на полпути и дам код на C #:

    static public IEnumerable<IList<T>> powerset<T>(IList<T> s)
    {
        int n = s.Count;
        int[] masks = new int[n];
        for (int i = 0; i < n; i++)
            masks[i] = (1 << i);
        for (int i = 0; i < (1 << n); i++)
        {
            List<T> newList = new List<T>(n);
            for (int j = 0; j < n; j++)
                if ((masks[j] & i) != 0)
                    newList.Add(s[j]);
            yield return newList;
        }
    }

Answer 2

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

Public class StrManipulation{

    public static void combinations(String suffix,String prefix){
        if(prefix.length()<0)return;
        System.out.println(suffix);
        for(int i=0;i<prefix.length();i++)
         combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
    }

    public static void main (String args[]){
        combinations("","12345");
        }
}

Answer 3

Простейшим алгоритмом генерации подмножеств набора размера N является учет всех двоичных чисел с использованием N битов Каждая позиция в номере представляет элемент из набора. Если бит в числе равен 1, соответствующий элемент набора находится в подмножестве, иначе элемент не входит в подмножество. Поскольку биты в числе упорядочены, это сохраняет порядок исходного набора.

Ссылки:

1. " Эффективное перечисление подмножеств набора "; Лаури, Хемерт и Шуфс
2. " Генерация подмножеств "; Репозиторий алгоритмов Stony Brook

Answer 4

В C ++ задана следующая процедура:

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Затем вы можете выполнить следующее:

std::string s = "12345";
for(std::size_t i = 1; i <= s.size(); ++i)
{
   do
   {
      std::cout << std::string(s.begin(),s.begin() + i) << std::endl;
   }
   while(next_combination(s.begin(),s.begin() + i,s.end()));
}

Answer 5

используя python, модуль itertools определяет метод комбинации (), который делает именно то, что вам нужно.

from itertools import *
list(combinations( '12345', 2 ))

даст вам:

[('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]

Answer 6

Для этого вы можете использовать следующий класс (в Java):

class Combinations {

  String input;
  StringBuilder cur;

  private void next(int pos, int reminder) {
    cur.append(input.charAt(pos));

    if (reminder == 1) {
      System.out.println(cur);
    } else {
      for (int i = pos + 1; i + reminder - 1 <= input.length(); i++)
        next(i, reminder - 1);
    }
    cur.deleteCharAt(cur.length() - 1);
  }

  public void generate(String input) {
    cur = new StringBuilder();
    this.input = input;
    for (int length = 1; length <= input.length(); length++)
      for (int pos = 0; pos + length <= input.length(); pos++)
        next(pos, length);
  }
}

Для запуска вашего примера используйте следующий код:

new Combinations().generate("12345");

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

Answer 7

Java-реализация ответа outis, принимающая входные строки в качестве аргументов.

import java.util.ArrayList;
import java.util.List;

public class Combo {

  public static void main(String[] args) {
    List<String> results = new ArrayList<String>();
    for ( int i = 1; i <= (1<<(args.length))-1; i++ ) {
      StringBuilder builder = new StringBuilder();
      for ( int j = 0; j < args.length; j++ ) {
        if ( (i & (1<<j)) != 0) {
          builder.append(args[j]);
        }
      }
      results.add(builder.toString());
    }
    System.out.println( results );
  }
}

Вот бег.

> javac Combo.java
> java Combo A B C
[A, B, AB, C, AC, BC, ABC]

Answer 8

Код для генерации всех возможных комбинаций строк приведен в Java. Все возможные комбинации строки длины 4 равны 2 ^ 4 (2 возведены в степень 4). В общем случае для строки длины n возможные комбинации равны 2 ^ n (2 возведены в степень n). Отсюда и код:

    class Perms
    {
    public void permsOfString(String a)
      {
     int x = 1;

     /* 
          Computes 2^string length

     */

     for(int i = 0;i<a.length() ;i++)
     {
         x = x * 2;
     }
     /*
            Iterate through all the possible combinations using a binary value of the number

      */
     for(int i = 1 ;i<x;i++)
     {

         String binStr = Integer.toBinaryString(i); // Convert i to binary string 
         for(int j = binStr.length() ; j <  a.length() ;j++)
         {
             binStr = "0"+binStr; // left pad with 0s
         }
   /*loop through the binary string if a character at the string is '1' note the    index,then display the character of the given string with that index */

          for(int k = 0; k <binStr.length();k++)
          {
             if(binStr.charAt(k) == '0') continue;
             else
             {
                 System.out.print(a.charAt(k));
             }

          }
         System.out.println();

     }

    }
    public static void main(String[]s)
  {
Perms p = new Perms();
p.permsOfString("abcd");
   }
} 

Answer 9

C ++ решение:

#include<iostream>
#include<string>

using namespace std;

int sub[10];

void next(int max, int length) {

    int pos = length - 1;

    //find first digit that can be increased
    while(pos >= 0)
    {
        if(sub[pos] == max - (length - 1 - pos))
            pos--;

        else
            break;
    }

        sub[pos]++; //increase digit

        //update other digits
        for(int a = pos+1; a < length; a++)
            sub[a] = sub[a-1] + 1;

}

int main()
{
    string word;
    cin >> word; 

    int max = word.length() - 1; //max value


    for(int n=1; n <= max+1; n++)
    {

        cout << n << "\n----\n";

        for(int i = 0; i < n; i++)
        {
            sub[i] = i;
        }

        for(int a = 0; ; a++)
        {               
            for(int b=0; b < n; b++)
                cout << word[sub[b]];

            cout << '\n';

            if(sub[0] == max - (n - 1))
                break;

            else
                next(max, n); //maximum value and last position
        }   

        cout << '\n';

    }   


    return 0;
 }
> for input :Sigma
> output is
1
----
s
i
g
m
a

2
----
si
sg
sm
sa
ig
im
ia
gm
ga
ma

3
----
sig
sim
sia
sgm
sga
sma
igm
iga
ima
gma

4
----
sigm
siga
sima
sgma
igma

5
----
sigma

Answer 10

C реализация

//Usage
combinations((char*)"",(char*)"12346897909787");


void combinations(char* suffix,char* prefix){
    if(NULL ==prefix || NULL == suffix){ return ;}
    int prefixLen = strlen(prefix);
    printf("\n[%s]",suffix);
    int slen  = strlen(suffix);
    char* s   = (char*)malloc(slen+2);
    s[slen+1] = '\0';
    for(int i=0;i<prefixLen;i++){
        strcpy(s,suffix);
        s[slen]  = prefix[i];
        int npfl = prefixLen-(i+1);
        char* p  = (char*) malloc(npfl+1);
        p[npfl]  = '\0';
        strcpy(p,prefix+i+1);
        combinations(s,p);
        free(p);
    }
    free(s);
}