5
$\begingroup$

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"}
Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
9
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. :-) $\endgroup$
    – Mr.Wizard
    Commented Sep 16, 2013 at 7:53
  • $\begingroup$ @Mr.Wizard The title of that question is "Replace For-loop with functional code" ;) So I suggested inefficient but in my opinion funny solution. $\endgroup$
    – ybeltukov
    Commented Sep 16, 2013 at 8:03
  • $\begingroup$ I understand now. $\endgroup$
    – Mr.Wizard
    Commented Sep 16, 2013 at 8:06
2
$\begingroup$

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}}
Improve this answer
$\endgroup$
2
  • $\begingroup$ For the size, one could also use Binomial[5,2] $\endgroup$
    – Pinguin Dirk
    Commented Sep 14, 2013 at 9:09
  • $\begingroup$ Yes, thank you @Pinguin, I sometimes forget how sophisticated Mathematica is and tend to use more elementary maths :) $\endgroup$
    – István Zachar
    Commented Sep 14, 2013 at 21:24
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.