Recently, a lot of people have expressed interest in generating all combinations and permutations of various objects. While this is a topic covered in second-year Computer Science courses, it seems a fair number of people have no idea how to go about generating them. In this post, I’ll provide code on how to go about doing this in an imperative language (Java). Doing it in a functional language like Haskell is much shorter, only 2 lines or so, but this version is imperative. Also, I’ve used strings, but feel free to modify it to any sort of container.
For generating combinations of length k, briefly:
- Extract the first element from the list
- Prepend it to all combinations of length k-1 from the leftover list
- Calculate all combinations of length k-1 from the leftover list.
For generating permutations of length k, briefly:
- Iterate over the list
- Remove one element at a time from the list
- Prepend the removed element to all permutations of length k-1 from the leftover list.
It’s really that simple, handle the base cases and you’re all set. Do a couple of examples on paper if you still don’t get it. Also, modifying the permutations code to generate all permuations with repetitions should be fairly simple too. Give it a shot.
Run my code to generate all combinations of my name:
Combinations c = new Combinations();
ArrayList<String> result = new ArrayList<String>();
String test = "viren";
for(int i = 1; i <= test.length(); i++){
result.clear();
result = c.getCombos(test,i);
System.out.println(result);
}
This results in:
[v, i, r, e, n]
[vi, vr, ve, vn, ir, ie, in, re, rn, en]
[vir, vie, vin, vre, vrn, ven, ire, irn, ien, ren]
[vire, virn, vien, vren, iren]
[viren]
And similarly, the permutations code results in:
[v, i, r, e, n]
[vi, vr, ve, vn, iv, ir, ie, in, rv, ri, re, rn, ev, ei, er, en, nv, ni, nr, ne]
[vir, vie, vin, vri, vre, vrn, vei, ver, ven, vni, vnr, vne, ivr, ive, ivn, irv, ire, irn, iev, ier, ien, inv, inr, ine, rvi, rve, rvn, riv, rie, rin, rev, rei, ren, rnv, rni, rne, evi, evr, evn, eiv, eir, ein, erv, eri, ern, env, eni, enr, nvi, nvr, nve, niv, nir, nie, nrv, nri, nre, nev, nei, ner]
[vire, virn, vier, vien, vinr, vine, vrie, vrin, vrei, vren, vrni, vrne, veir, vein, veri, vern, veni, venr, vnir, vnie, vnri, vnre, vnei, vner, ivre, ivrn, iver, iven, ivnr, ivne, irve, irvn, irev, iren, irnv, irne, ievr, ievn, ierv, iern, ienv, ienr, invr, inve, inrv, inre, inev, iner, rvie, rvin, rvei, rven, rvni, rvne, rive, rivn, riev, rien, rinv, rine, revi, revn, reiv, rein, renv, reni, rnvi, rnve, rniv, rnie, rnev, rnei, evir, evin, evri, evrn, evni, evnr, eivr, eivn, eirv, eirn, einv, einr, ervi, ervn, eriv, erin, ernv, erni, envi, envr, eniv, enir, enrv, enri, nvir, nvie, nvri, nvre, nvei, nver, nivr, nive, nirv, nire, niev, nier, nrvi, nrve, nriv, nrie, nrev, nrei, nevi, nevr, neiv, neir, nerv, neri]
[viren, virne, viern, vienr, vinre, viner, vrien, vrine, vrein, vreni, vrnie, vrnei, veirn, veinr, verin, verni, venir, venri, vnire, vnier, vnrie, vnrei, vneir, vneri, ivren, ivrne, ivern, ivenr, ivnre, ivner, irven, irvne, irevn, irenv, irnve, irnev, ievrn, ievnr, iervn, iernv, ienvr, ienrv, invre, inver, inrve, inrev, inevr, inerv, rvien, rvine, rvein, rveni, rvnie, rvnei, riven, rivne, rievn, rienv, rinve, rinev, revin, revni, reivn, reinv, renvi, reniv, rnvie, rnvei, rnive, rniev, rnevi, rneiv, evirn, evinr, evrin, evrni, evnir, evnri, eivrn, eivnr, eirvn, eirnv, einvr, einrv, ervin, ervni, erivn, erinv, ernvi, erniv, envir, envri, enivr, enirv, enrvi, enriv, nvire, nvier, nvrie, nvrei, nveir, nveri, nivre, niver, nirve, nirev, nievr, nierv, nrvie, nrvei, nrive, nriev, nrevi, nreiv, nevir, nevri, neivr, neirv, nervi, neriv]
Without further ado, here’s the source code. As always, if you find any bugs or have suggestions for improvements, let me know.
