Алгоритм минимального изменения, который максимизирует "обмен"

Question

Это вопрос о комбинаторике от нематематика, поэтому, пожалуйста, постарайтесь потерпеть меня!

Учитывая массив из n различных символов, я хочу создать подмножества из k символов в порядке минимального изменения, то есть в порядке, в котором поколение i + 1 содержит ровно один символ, которого не было в поколении i. Это не так уж сложно само по себе. Однако я также хочу максимизировать количество случаев, когда символ, который был заменен out в поколении i + 1, является тем же самым символом, который был заменен в в поколении i. Для иллюстрации, при n = 7, k = 3:

abc abd abe * abf * abg * afg aeg * adg * acg * acd ace * acf * aef adf * ade bde bdf bef bcf * bce bcd * bcg * bdg beg * bfg * cfg ceg * cdg * cde cdf * cef def deg dfg efg

Строки, отмеченные звездочкой, указывают на случай, который я хочу увеличить; например e, новое в поколении 3, abe, заменяет d, которое было новым в поколении 2, abd. Кажется невозможным, чтобы это произошло в каждом поколении, но я хочу, чтобы это происходило как можно чаще.

Типичные размеры массивов, которые я использую, составляют 20-30, а размеры подмножеств около 5-8.

Я использую странный язык, Icon (или фактически его производное Unicon ), поэтому я не ожидаю, что кто-либо опубликует код, который я смог бы использовать напрямую. Но я буду благодарен за ответы или подсказки в псевдокоде, и сделаю все возможное, чтобы перевести C и т. Д. Кроме того, я заметил, что проблемы такого рода часто обсуждаются в терминах массивов целых чисел, и я, безусловно, могу применить решения размещены в таких терминах к моей собственной проблеме.

Спасибо

Ким Бастин

Изменить 15 июня 2010 г .:

Кажется, я попал в более глубокую воду, чем думал, и хотя я благодарен за все ответы, не все из них были актуальны. В качестве примера решения, которое НЕ является адекватным, позвольте мне опубликовать мою собственную процедуру Unicon для генерации k-арных подмножеств набора символов s в минимальном порядке изменения. Чтобы понять код, вам необходимо знать следующее: предопределенный * означает размер структуры, поэтому, если s является строкой, * s означает размер s (количество символов, которое она содержит). || является операцией конкатенации строк Предлог! производит каждый элемент структуры, например, каждый символ строки, в свою очередь, на последовательных проходах. И управляющая структура «suspend» возвращает результат из процедуры, но оставляет процедуру «в ожидании» со всеми локальными переменными на месте, так что новые результаты могут быть получены, если процедура вызывается в цикле.

procedure revdoor(s, k)  
# Produces all k-subsets of a string or character set s in a 'revolving  
# door' order. Each column except the first traverses the characters  
# available to it in alphabetical and reverse alphabetical order  
# alternately. The order of the input string is preserved. 
# If called in a loop as revdoor("abcdefg", 3), 
# the order of production is: abc, abd, abe, abf, abg, acg, acf, ace, acd,  
# ade, adf, adg, aeg, aef, afg, bfg, bef, beg, bdg, bdf, bde, bcd, bce,  
# bcf, bcg, cdg, cdf, cde, cef, ceg, cfg, dfg, deg, def, efg  

local i  
static Ctl  

if /Ctl then {             # this means 'if Ctl doesn't exist'
  if k = 0 then return ""  
  Ctl := list(k, 1)        # a list of k elements, each initialised to 1.
}  

if Ctl[k] = 1 then {  
  if k = 1 then suspend !s else  
    every i := 1 to *s-k+1 do {  
      suspend s[i] || revdoor(s[i+1:0], k-1)  
    }   
  } else {  
    if k = 1 then suspend !reverse(s) else  
    every i := -k to -*s by -1 do {  
      suspend s[i] || revdoor(s[i+1:0], k-1)  
    }  
  }  

  # the following line multiplies element k of Ctl by -1 if k < size of Ctl
  # (this controls the order of generation of characters), 
  # and destroys Ctl on final exit from the procedure.
  if k < *Ctl then Ctl[k] *:= -1 else Ctl := &null   

end  

Обратите внимание, что вывод описанной выше процедуры не является оптимальным в моем смысле. Один из результатов моих исследований до сих пор состоит в том, что максимальная «оценка обмена» для списка k-арных подмножеств из n элементов не меньше, чем comb (n-1, k), или в случае n = 7, k = 3, максимальный балл равен по крайней мере гребне (6, 3) = 20. Я определяю «обменный балл» списка как количество элементов в списке, новый элемент которого заменяет элемент в предыдущем элементе, который сам по себе был новым. У меня нет математического оборудования, чтобы доказать это, но это легко увидеть при k = 1 или k = 2. Для некоторых (n, k) возможен немного более высокий балл, как в случае n = 7, k = 3:

abc abd abe abf abg
acg adg aeg afg
efg dfg cfg bfg
Прошу БДГ БЦГ
bcd bce bcf
bdf bef
def cef aef
ADF ACF
ACD ACE
ADE
бдэ кдэ
cdf cdg
КЭГ
градус (обменный балл = 21)

Можно отметить, что приведенный выше список находится в «строгом минимальном порядке изменений» (например, слово «гольф»: новый персонаж всегда находится в той же позиции, что и заменяемый персонаж), что может указывать направление, в котором движется моя собственная работа. , Я надеюсь опубликовать что-то еще через несколько дней.

Kim

Answer 1

Это довольно просто.Чтобы добиться максимальной замены, просто думайте о символах как о числах и увеличивайте строку на единицу, пока не достигнете верхнего предела.Затем убедитесь, что вы не используете один и тот же символ дважды в строке.Я думаю, что это будет работать:

char c[] = {'a', 'b', 'c', 'd', 'e'};
const int n = 5;
const int k = 3;
char s[k];

void print()
{
    for( int i = 0; i < k; ++i )
        putchar(c[s[i]]);
    putchar('\n');
}

bool increment( int m )
{
    // reached the limit?
    if( ++s[m] == n && m == 0 )
        return false;

    next:   
    for( int i = 0; i < m; ++i )
    {
        if( s[m] == n )
        {
            // carry
            s[m] = 0;
            if( !increment( m-1 ))
                return false;
            goto next;
        }
        else if( s[i] == s[m] )
        {
            // the character is already used
            ++s[m];
            goto next;
        }   
    }
    return true;
}

int main(int, char**)
{   
    // initialise
    for( int i = 0; i < k; ++i )
        s[i] = i;

    // enumerate all combinations
    do
        print();
    while(increment(k-1));
}

Answer 2

Я работал над этой проблемой в 2010 году, но тогда не смог найти решение.Несколько дней назад я еще раз взглянул на некоторые из моих записей того времени и подозревал, что был очень близок к решению.Через несколько минут у меня был ключ.

Чтобы подвести итоги: требуется строгое минимальное изменение порядка k-подмножеств строки s, чтобы LIFO (последний пришел первым вышел) был максимизирован.Я называю это «максимальным обменом» в более ранних публикациях.

Я называю алгоритм maxlifo (максимизированный LIFO) после требования ключа.Он принимает два параметра: строку s, которая не должна содержать повторяющихся символов, и положительное целое число k, не превышающее размер s.Алгоритм является рекурсивным, то есть maxlifo (s, k) использует вывод maxlifo (s, k-1) вплоть до k = 1.Вывод возвращается в виде списка.

Ниже я приведу неформальное объяснение, с примерами, используя строку «abcdefg» и различные значения k.Далее следует пример реализации в качестве процедуры Unicon.(Я не владею ни одним из наиболее часто используемых языков.)

Случай k = 1 тривиален - он возвращает элементы s в порядке от первого до последнего.

Дляk> 1, примените следующие правила к выводу maxlifo (s, k-1):

(1) Для каждого элемента вывода maxlifo (s, k-1) список в строкеk-подмножества, построенные из этого элемента, с каждым пропущенным символом s по очереди.Порядок символов в подмножествах такой же, как в s.

(2) Работая от второй строки вниз, замените пустые «заполнители» для всех вхождений подмножеств, которые появляются в более ранней строке.Теперь каждое k-подмножество s появляется только один раз.

(3) В каждой непустой строке отметьте начальную букву!каждое подмножество так, чтобы в следующей строке был заполнитель в той же позиции.Эта маркировка означает «первый».Ровно одно подмножество будет помечено в каждой непустой строке.

(4) Удалите все пустые строки (содержат только заполнители).

(5) В каждой оставшейся строке, кромепоследнее, отметьте финалом!подмножество в позиции, соответствующей подмножеству, помеченному как «первый» в следующей нижней строке.Эта маркировка означает «последний».

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

(6) В каждой строке сверху вниз:

(6.1) Удалите все пустые заполнители.

(6.2) Добавьте в список вывода подмножество, помеченное как «первое» (начальное!), И удалите его из строки.

(6.3) Если в строке еще есть подмножествалибо самое левое, либо самое правое подмножество будет помечено как «последний» (последний!).Если крайнее правое подмножество помечено как «последнее», добавьте подмножества в список вывода по порядку слева направо, в противном случае по порядку справа налево.

(7) После обработки всех строк верните список вывода.

Пример использования maxlifo ("abcdefg", 2):

Col1 содержит вывод maxlifo ("abcdefg", 1).Строки Col2 содержат клики, образованные с оставшимися символами s:

Col1    Col2
----    ----------------------------
a       ab   ac   ad   ae   af   ag
b       ab   bc   bd   be   bf   bg
c       ac   bc   cd   ce   cf   cg
d       ad   bd   cd   de   df   dg
e       ae   be   ce   de   ef   eg
f       af   bf   cf   df   ef   fg
g       ag   bg   cg   dg   eg   fg

Выделить подмножества, которые появляются в более ранней строке:

a       ab   ac   ad   ae   af   ag
b            bc   bd   be   bf   bg
c                 cd   ce   cf   cg
d                      de   df   dg
e                           ef   eg
f                                fg
g                               

Отметить «первое» подмножество вкаждая строка (строка с пробелом под ней):

a      !ab   ac   ad   ae   af   ag
b           !bc   bd   be   bf   bg
c                !cd   ce   cf   cg
d                     !de   df   dg
e                          !ef   eg
f                               !fg
g                               

Удалить все полностью пустые строки (в данном случае только одну):

a      !ab   ac   ad   ae   af   ag
b           !bc   bd   be   bf   bg
c                !cd   ce   cf   cg
d                     !de   df   dg
e                          !ef   eg
f                               !fg

Отметить «последнее» подмножество вкаждая строка (та, у которой под первым «подмножеством»).

a      !ab   ac!  ad   ae   af   ag
b           !bc   bd!  be   bf   bg
c                !cd   ce!  cf   cg
d                     !de   df!  dg
e                          !ef   eg!
f                               !fg

Выведите каждую строку в порядке, описанном выше: «first», без опознавательных знаков, «last»:

                                               Ordered rows:
a      !ab   ac!  ad   ae   af   ag            ab ag af ae ad ac
b           !bc   bd!  be   bf   bg            bc bg bf be bd
c                !cd   ce!  cf   cg            cd cg cf ce
d                     !de   df!  dg            de dg df
e                          !ef   eg!           ef eg
f                               !fg            fg

Вывод: [ab ag af ae ad ac bc bg bf быть bd cd cg cf ce df dg de ef, например, fg]

Примеры для 3 <= k <= 6 приведены менее подробно.Пустые строки, удаленные на шаге 4, остаются на месте. </p>

maxlifo ("abcdefg", 3):

                                                       Ordered rows:
ab     !abc   abd   abe   abf   abg!                   abc abd abe abf abg
ag            acg   adg   aeg! !afg                    afg acg adg aeg
af            acf   adf! !aef                          aef acf adf
ae            ace! !ade                                ade ace
ad           !acd!                                     acd
ac                     
bc           !bcd   bce   bcf   bcg!                   bcd bce bcf bcg
bg                  bdg   beg! !bfg                    bfg bdg beg
bf                  bdf! !bef                          bef bdf
be                 !bde!                               bde 
bd                                  
cd                 !cde   cdf   cdg!                   cde cdf cdg
cg                        ceg! !cfg                    cfg ceg
cf                       !cef!                         cef
ce                             
de                       !def   deg!                   def deg
dg                             !dfg!                   dfg
df                             
ef                             !efg                    efg
eg                       
fg                       

Вывод: [abc abd abe abf abg afg acg adg aeg aef acfadf ade ace acd
bcd bce bcf bcg bfg bdg beg bef bdf bde cde cdf cdg cfg ceg cef def deg dfg efg]

maxlifo ("abcdefg", 4):

                                            Ordered rows:
abc         !abcd  abce!  abcf   abcg       abcd abcg abcf abce
abd               !abde   abdf!  abdg       abde abdg abdf
abe                      !abef   abeg!      abef abeg
abf                             !abfg!      abfg
abg                                   
afg                acfg!  adfg  !aefg       aefg adfg acfg
acg               !acdg   aceg!             acdg aceg
adg                      !adeg!             adeg
aeg                                  
aef                acef! !adef              adef acef
acf               !acdf!                    acdf
adf                                  
ade               !acde!                    acde
ace                                   
acd                                   
bcd               !bcde   bcdf!  bcdg       bcde bcdg bcdf
bce                      !bcef   bceg!      bcef bceg
bcf                             !bcfg!      bcfg
bcg                                  
bfg                       bdfg! !befg       befg bdfg
bdg                      !bdeg!             bdeg
beg                                  
bef                      !bdef!             bdef
bdf                                  
bde                                  
cde                      !cdef   cdeg!      cdef cdeg
cdf                             !cdfg!      cdfg
cdg                                   
cfg                             !cefg!      cefg
ceg                                  
cef                                  
def                             !defg       defg
deg                          
dfg                          
efg                          

Вывод: [abcd abcg abcf abce abde abdg abdf abef abeg abfg aefg adfg acfg acdg aceg adeg adef acef acdf acde bcde bcdg bcdf bcef bceg bcfg befg bdfg bdeg bdef cdef cdeg cdfg cefg DEFG]

maxlifo ("abcdefg", 5):

                                            Ordered rows:
abcd       !abcde   abcdf   abcdg!          abcde abcdf abcdg 
abcg                abceg! !abcfg           abcfg abceg 
abcf               !abcef!                  abcef 
abce                                
abde               !abdef   abdeg!          abdef abdeg 
abdg                       !abdfg!          abdfg 
abdf                         
abef                       !abefg!          abefg 
abeg                         
abfg                         
aefg                acefg! !adefg           adefg acefg 
adfg               !acdfg!                  acdfg 
acfg                         
acdg               !acdeg!                  acdeg 
aceg                         
adeg                         
adef               !acdef!                  acdef 
acef                         
acdf                         
acde                         
bcde               !bcdef   bcdeg!          bcdef bcdeg 
bcdg                       !bcdfg!          bcdfg 
bcdf                         
bcef                       !bcefg!          bcefg 
bceg                         
bcfg                         
befg                       !bdefg!          bdefg 
bdfg                         
bdeg                         
bdef                         
cdef                       !cdefg           cdefg 
cdeg                         
cdfg                         
cefg                         
defg                         

Вывод: [abcde abcdf abcdg abcfg abceg abcef abdef abdef abdeg abdfg abefg adefg acefg acdfg acdeg acdef bcdef bcdeg bcdfg bcefg bdefg cdefg]

maxlifo ("abcdefg", 6):

                                            Ordered rows:
abcde               !abcdef   abcdeg!       abcdef abcdeg 
abcdf                        !abcdfg!       abcdfg 
abcdg                               
abcfg                        !abcefg!       abcefg 
abceg                              
abcef                               
abdef                        !abdefg!       abdefg 
abdeg                               
abdfg                               
abefg                               
adefg                               
acefg                        !acdefg!       acdefg 
acdfg                               
acdeg                               
acdef                               
bcdef                        !bcdefg        bcdefg 
bcdeg                               
bcdfg                               
bcefg                               
bdefg                               
cdefg                        

Вывод: [abcdef abcdeg abcdfg abcefg abdefg acdefg bcdefg]

Реализация Unicon:

procedure maxlifo(s:string, k:integer)
# A solution to my combinatorics problem from 2010.
# Return a list of the k subsets of the characters of a string s
# in a minimal change order such that last-in first-out is maximised.
# String s must not contain duplicate characters and in the present 
# implementation must not contain "!", which is used as a marker.

  local ch, cand, Hit, inps, i, j, K, L, Outp, R, S

  # Errors
  if *cset(s) ~= *s then 
    stop("Duplicate characters in set in maxlifo(", s, ", ", k, ")")
  if find("!", s) then 
    stop("Illegal character in set in maxlifo(", s, ", ", k, ")")
  if k > *s then 
    stop("Subset size larger than set size in maxlifo(", s, ", ", k, ")")

  # Special cases
  if k = 0 then return []
  if k = *s then return [s]

  Outp := []
  if k = 1 then {
    every put(Outp, !s)
    return Outp
  }

  # Default case
  S := set()
  K := []

  # Build cliques from output of maxlifo(s, k-1) with the remaining 
  # characters in s, substituting empty strings as placeholders for 
  # subsets already listed.
  every inps := !maxlifo(s, k-1) do { 
    R := []
    every ch := !s do
      if not find(ch, inps) then {
        cand := reorder(inps ++ ch, s)
        if member(S, cand) then cand := "" else insert(S, cand)
        put(R, cand)
      }
    put(K, R)
  }

  # Mark ‘first’ subset in each row with initial "!"
  every i := 1 to *K - 1 do {
    every j := 1 to *K[i] do
      if K[i, j] ~== "" & K[i+1, j] == "" then {
        K[i, j] := "!" || K[i, j]
        break
      }
  }

  # Remove rows containing only placeholders
  every i := *K to 1 by -1 do {
    every if !K[i] ~== "" then break next
    delete(K, i)  
  }

  # Mark ‘last’ subset in each row with final "!"
  every i := 1 to *K - 1 do 
    every j := 1 to *K[i] do 
      if K[i+1, j][1] == "!" then {
        K[i, j] ||:= "!"
        break
      }

  # Build output list
  every R := !K do {

    # Delete placeholders from row (no longer needed and in the way)
    every j := *R to 1 by -1 do if R[j] == "" then delete(R, j)

    # Handle ‘first’ subset and remove from row
    # N.B. ‘First’ subset will be leftmost or rightmost in row
    if R[1][1] == "!" then 
      put(Outp, trim(get(R), '!', 0)) 
      else put(Outp, trim(pull(R), '!', 0))   

    # Handle any remaining subsets, ‘last’ subset last, stripping '!' markers
    # N.B. ‘Last’ subset will be leftmost or rightmost in row after removal
    # of ‘first’ subset.
    if R[-1][-1] == "!" then while put(Outp, trim(get(R), '!', 0)) else
      while put(Outp, trim(pull(R), '!', 0))
  }

  return Outp

end


procedure reorder(cs:cset, s:string)
# Reorder cset cs according to string s

  local r
  # If no s, return set in alphabetical order
  if /s then return string(cs)

  r := ""
  s ? while tab(upto(cs)) do r ||:= move(1)
  return r

end

Answer 3

Для хорошего ответа, будет ли приемлемым одновременное вычисление списка комбинаций, или вам нужно вычислять их по одному? Другими словами, нужна ли вам функция:

Combination nextCombo();

или будет

vector<Combination> allCombinations();

быть приемлемым?

Если вычисление комбинаций в пакете допустимо, возможно, что итеративно-углубленный поиск A * (или просто поиск A *, но я подозреваю, что он исчерпал бы память), сработал бы. При допустимой эвристике A * гарантированно даст оптимальное значение. У меня мало времени, поэтому я решил опубликовать этот частичный ответ и отредактировать сообщение, если у меня будет время написать код.

A * - алгоритм поиска графа. В этом случае узлы представляют собой списки комбинаций, используемых до сих пор (дубликаты в списке не допускаются). Мой план состоял в том, чтобы использовать строковое представление для узлов. n = 30 вписывается в 32-битное целое число. Мы можем произвольно переставить любое решение так, чтобы первая комбинация начиналась с 0 и заканчивалась на 1, то есть 000 ... 1111. Узел с более коротким списком соединяется с более длинным, если два списка одинаковы вплоть до последнего элемента, а последний элемент отличается только тем, что один 0'бит перевернут на 1, а один 1 бит перевернут на 0. расстояние между ними равно 0, если произошел обмен, и 1, если произошел обмен.

Вторым представлением для каждой комбинации является отсортированный список включенных битов. Одной из возможных допустимых эвристик для этого графа является использование этого списка индексов. Каждый раз (в списке комбинаций) индекс используется в определенной позиции в списке индексов, отметьте его. Количество позиций с неиспользованными индексами - текущий последний измененный индекс - это (я считаю) минимальное количество свопов, которое должно произойти.

Чтобы проиллюстрировать эту эвристику, рассмотрим последовательность abc abd abe * abf * abg afg сверху. (буквы будут цифрами в моем обращении, но это небольшая разница). Эта последовательность (которая будет одним узлом в графе поиска) будет иметь следующие отмеченные места:

 1   2   3
*a      
 b  *b   
 c   c  *c
 d   d  *d
 e   e  *e
    *f  *f
        *g

Таким образом, эвристика может предсказать, что требуется как минимум один обмен (поскольку в позиции 3 нет неотмеченных элементов, а текущая позиция равна 2).

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

---

Re: результат полноты NP (в комментарии к ответу Зака ​​Томпсона). Граф, на котором мы ищем гамильтонову траекторию с минимальными затратами, имеет совершенно особую структуру. Например, нормально NP-полная задача о гамильтоновом пути может быть решена за O (n) время с помощью алгоритма «перечислить все комбинации», где n - это число узлов в графе. Эта структура делает возможным, что, хотя на общем графе покрытие вершин является жестким, на вашем графе оно может быть полиномиальным (даже линейным или квадратичным). Конечно, поскольку граф имеет много узлов, например, для n = 30, k = 8, возможно, вам еще предстоит много вычислений.

Answer 4

Вместо того, чтобы начать с алгоритма, я попытался найти способ найти форму для максимального «обменного счета», чтобы вы знали, для чего нужно стрелять. Часто алгоритм для получения желаемой структуры может возникнуть из такого доказательства.

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

Я начал с представления набора комбинаций в виде вершин на графе с ребрами, соответствующими «смежности» (разность только одного элемента) комбинаций. Итак:

• вершины n выбирают k
• каждая вершина имеет степень k (n-k)
• количество ребер = "n выбрать k" * k (n-k) / 2 = "n выбрать 2" * "n-2 выбрать k-1"

В этих графиках много симметрии. График для всех заданных {n, k} такой же, как и для {n, n-k}. Если k = 1 или k = n-1, то это полный граф на n вершинах (каждая комбинация отличается от всех других только одним символом). Хотя я не вижу очевидного алгоритма из этого.

Редактировать: Моей следующей мыслью было представить график с несколько иной интерпретацией. Вы можете думать о каждой {n, k} -комбинации как о последовательности из n битов, где есть k 1s. Позиция 1 соответствует тому, какой из n символов присутствует в комбинации. Таким образом, для n = 7 k = 3 abc равно 1110000, adg равно 1001001, efg равно 0000111. При этом вы также можете представить точки, лежащие в углах n-мерного гиперкуба. Таким образом, для данной подпоследовательности ребра соответствуют вашим критериям "минимального обмена", если они копланарны: я думаю о них как о "режущих плоскостях" через гиперкуб.

Вы ищете гамильтонов путь по этому графику комбинаций, который соответствует вашим особым критериям.

Еще один способ подумать о вашей проблеме - минимизировать количество раз в последовательности, которую вы делаете меняете, какой символ в комбинации изменяется.

Answer 5

Ким, описание вашей проблемы очень похоже на попытку (домашнее задание) описать простейшее решение для перечисления всех k-комбинаций набора из n элементов - без слишком простого выделения фактического решения. Во всяком случае, смотрите ниже мой выстрел. Я использовал Java, но важные части не отличаются от C.

public class Homework
{
  /**
   * Prints all k-combinations of a set of n elements. Answer to this 
   * question: http://stackoverflow.com/questions/2698551
   */
  public static void main(String[] args)
  {
    Combinations combinations = new Combinations(7, 3);
    System.out.printf(
        "Printing all %d %d-combinations of a set with %d elements:\n", 
        combinations.size(), combinations.k, combinations.n);
    for (int[] c : combinations)
      System.out.println(Arrays.toString(c));
  }

  /**
   * Provides an iterator for all k-combinations of a set of n elements. 
   */
  static class Combinations implements Iterable<int[]>  
  {
    public final int n, k;

    public Combinations(int n, int k)
    {
      if (n < 1 || n < k)
        throw new IllegalArgumentException();
      this.n = n;
      this.k = k;
    }

    @Override
    public Iterator<int[]> iterator()
    {
      return new Iterator<int[]>()
      {
        private int[] c;

        @Override
        public void remove() { throw new UnsupportedOperationException(); }

        @Override
        public int[] next()
        {
          if (c == null)
          {
            c = new int[k];
            for (int i = 0; i < k; i++)
              c[i] = i;
          }
          else
          {
            int i = c.length - 1;
            while (i >= 0 && c[i] == n - k + i)
              i--;

            if (i < 0)
              throw new NoSuchElementException();

            c[i]++;
            for (int j = i + 1; j < c.length; j++)
              c[j] = c[i] + j - i;
          }
          return c.clone(); // remove defensive copy if performance is more important
        }

        @Override
        public boolean hasNext() { return c == null || c[0] < n - k; }
      };
    }

    /**
     * Returns number of combinations: n! / (k! * (n - k)!).
     */
    public BigInteger size()
    {
      BigInteger s = BigInteger.valueOf(n);
      for (int i = n - 1; i > n - k; i--)
        s = s.multiply(BigInteger.valueOf(i));
      for (int i = k; i > 1; i--)
        s = s.divide(BigInteger.valueOf(i));
      return s;
    }
  }
}

Вот вывод для вашего примера:

Printing all 35 3-combinations of a set with 7 elements:
[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 1, 6] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 2, 6] [0, 3, 4] 
[0, 3, 5] [0, 3, 6] [0, 4, 5] [0, 4, 6] [0, 5, 6] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 2, 6] [1, 3, 4] 
[1, 3, 5] [1, 3, 6] [1, 4, 5] [1, 4, 6] [1, 5, 6] [2, 3, 4] [2, 3, 5] [2, 3, 6] [2, 4, 5] [2, 4, 6] 
[2, 5, 6] [3, 4, 5] [3, 4, 6] [3, 5, 6] [4, 5, 6]