Скажем, у меня есть строка "12345". Я должен получить все комбинации подпоследовательностей этой строки, такие как:
Обратите внимание, что я сгруппировал их в разных количествах символов, но не изменил их порядок. Мне нужен метод/функция.
Вам нужен комплект питания. Вот все вопросы о 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;
}
}
Простейшим алгоритмом для генерации подмножеств множества размера N является рассмотрение всех двоичных чисел с использованием N бит. Каждая позиция в числе представляет элемент из набора. Если бит в числе равен 1, соответствующий элемент набора находится в подмножестве, иначе элемент не находится в подмножестве. Поскольку биты в числе упорядочены, это сохраняет порядок исходного набора.
Литература:
способ чистого подхода может быть достигнут путем рекурсии следующим образом.
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");
}
}
В С++ задана следующая процедура:
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()));
}
используя 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')]
Вы можете использовать следующий класс для этого (в 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");
Порядок вывода такой же, как в примере. Он не требует хранения всех подмножеств, а затем сортировки, чтобы получить описанный вами порядок.
Реализация 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]
Код для генерации всех возможных комбинаций строк указан в 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");
}
}
Ответ 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)).)
Реализация 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);
}
Решение С++:
#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
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
Мик.
Теперь я вижу, вы хотели подмножества, а не подписок.