# How can I generate permutations of bit strings with repetition?

How can I write a function which has two parameters and it should generate combination of arbitrary range bits, for example: function[n, k], with n being range, k being number of 1 digits. If I define n = 4 and k = 2, the function should return the following set (in any order):

function[4, 2]

{"1100", "1010", "1001", "0110", "0011", "0101"}


You could e.g. do it like that:

f[n_, k_] := Permutations[Join[ConstantArray[1, k], ConstantArray[0, n - k]]]


and then format it to your liking

• thank you very much. it is working – user2777109 Sep 13 '13 at 20:22
• Just to make it more compact: Permutations[PadLeft[ConstantArray[1, k], n]] – Kuba Sep 13 '13 at 20:25
• Or Permutations@UnitStep@Range[k-n, k-1] – ybeltukov Sep 13 '13 at 20:31
• @ybeltukov While mine is a little improvement, yours deserves separate answer I think :) – Kuba Sep 13 '13 at 20:31
• @Kuba Now it grows up into the separate answer :) – ybeltukov Sep 13 '13 at 21:52

As I wrote in comment there are a more compact form of Pinguin Dirk answer:

f[n_, k_] := Permutations@UnitStep@Range[k-n, k-1]


However, Permutations is not a panacea. Let us consider straightforward approach

f2[n_, k_] :=
Module[{res = ConstantArray[0, {Binomial[n, k], n}], pos = 0},
With[{kk = Sequence @@ Table[Unique["k"], {k}]},
With[{lim = Sequence @@ Transpose@{{kk}, Range[k, 1, -1], Prepend[Most@{kk} - 1, n]}},
Do[res[[++pos, {kk}]] = 1;, lim]; res]]];


For small k it is much faster then Permutations!

f[500, 2]; // AbsoluteTiming // First
f2[500, 2]; // AbsoluteTiming // First


30.356745

0.797071

• It's funny I should find this now, after your inefficient use of Permutations here; I see you are not unaware of the problem. Why not use a method more like this one for that more recent question? Anyway +1 on this. :-) – Mr.Wizard Sep 16 '13 at 7:53
• @Mr.Wizard The title of that question is "Replace For-loop with functional code" ;) So I suggested inefficient but in my opinion funny solution. – ybeltukov Sep 16 '13 at 8:03
• I understand now. – Mr.Wizard Sep 16 '13 at 8:06

Since we are dealing here with permutations with repetition, we can always compute the size of the set without actually generating the set:

{n, k} = {5, 2};
size = n!/(k! (n - k)!)

10


If k = 2 is fixed, we can use the sequence of A018900 from OIES to extract the first 10 elements and convert them to binaries:

seq = Take[WolframAlpha["A018900", {{"Continuation", 1}, "ComputableData"}], size]
IntegerDigits[#, k, n] & /@ seq

{3, 5, 6, 9, 10, 12, 17, 18, 20, 24}

{{0, 0, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 1, 0, 0, 1},
{0, 1, 0, 1, 0}, {0, 1, 1, 0, 0}, {1, 0, 0, 0, 1}, {1, 0, 0, 1, 0},
{1, 0, 1, 0, 0}, {1, 1, 0, 0, 0}}

• For the size, one could also use Binomial[5,2] – Pinguin Dirk Sep 14 '13 at 9:09
• Yes, thank you @Pinguin, I sometimes forget how sophisticated Mathematica is and tend to use more elementary maths :) – István Zachar Sep 14 '13 at 21:24

StringJoin@ReplacePart[ConstantArray["0",n],List/@#->"1"]&/@Subsets[Range@n,{k}]