Как получить все подпоследовательные комбинации String (в Java, или С++ и т.д.)

Ответ 1

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

Вот базовая реализация в 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, поэтому я встречу вас на полпути и дам вам код на С#:

    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;
        }
    }

Ответ 2

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

Литература:

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

Ответ 3

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

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");
        }
}

Ответ 4

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

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()));
}

Ответ 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')]

Ответ 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");

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

Ответ 7

Реализация Java outis 'отвечает, принимая входные строки как args.

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]

Ответ 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");
   }
} 

Ответ 9

Ответ Adrien Plisson показывает, как извлекать все подпоследовательности указанной длины в Python (для произвольных типов данных последовательности). ОП указывает, что он работает со строками и что он хочет все подпоследовательности. Таким образом, используя itertools.combinations, мы определяем:

>>> from itertools import combinations
>>> def subseq_combos(inp):
...     return (''.join(s) for r in range(len(inp) + 1) for s in combinations(inp, r))
... 
>>> list(subseq_combos('12345'))
['', '1', '2', '3', '4', '5', '12', '13', '14', '15', '23', '24', '25', '34', '35', '45', '123', '124', '125', '134', '135', '145', '234', '235', '245', '345', '1234', '1235', '1245', '1345', '2345', '12345']

(Если пустую подпоследовательность следует опустить, используйте range(1, len(inp) + 1)).)

Ответ 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);
}

Ответ 11

Решение С++:

#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

Ответ 12

oops, неправильный ответ:

<Я > Подпоследовательности определенной длины в Python:

def subseqs(seq, length):
    for i in xrange(len(seq) - length + 1):
        yield seq[i:i+length]

Используется следующим образом:

for each in subseqs("hello", 3):
    print each

печатает:

hel
ell
llo

Чтобы сгенерировать все подпоследовательности, выполните следующее:

for i in xrange(len("hello")):
    for each in subseqs("hello", i + 1):
        print each

печатает:

h
e
l
l
o
he
el
ll
lo
hel
ell
llo
hell
ello
hello

Мик.

Теперь я вижу, вы хотели подмножества, а не подписок.