Alle Binärkombinationen auf Dezimal

12

Haftungsausschluss

Diese Frage ist kein Duplikat dieser Frage . Ich zähle keine bestimmten Ziffern, da wir diese bereits in den Anfangsparametern festgelegt haben. Diese Frage konzentriert sich auf die Dezimalzahlen, die aus den binären Zeichenfolgen basierend auf den angegebenen Ziffern erstellt werden können.

Herausforderung

Berechnen Sie bei zwei Ganzzahlen Xund entsprechend Yder Anzahl der Nullen ( 0) und Einsen ( 1) alle möglichen Dezimaläquivalente, die aus der Erstellung von Binärzeichenfolgen unter Verwendung der angegebenen Nullen und Einsen ermittelt werden können, und zeigen Sie sie als Ausgabe an.

Beispiel 1:

Eingang: 0 1

Ausgabe: 1

Erläuterung: Es muss nur eine 1berücksichtigt werden, die nur in eine Richtung konvertiert werden kann.

Beispiel 2:

Eingang: 1 1

Ausgabe: 1,2

Erklärung: 01konvertiert zu 1, 10konvertiert zu 2.

Beispiel 3:

Eingang: 3 2

Ausgabe: 3,5,6,9,10,12,17,18,20,24

Erklärung: Drei 0s und zwei 1s ergeben 00011(3), 00101(5), 00110(6), 01001(9), 01010(10), 01100(12), 10001(17), 10010(18), 10100(20), 11000(24)

Einschränkungen und Regeln

  • Ich erwarte nur, dass Ihr Code funktioniert, wo 0 < X + Y <= 16also die maximale Anzahl in der Ausgabe erst ab 16 1s auftreten kann, also Parameter 0und 16.
  • Aufgrund der obigen Einschränkung ist der erwartete Zahlenbereich in der Ausgabe von 0und 65535.
  • Ich akzeptiere Funktionen oder Code, solange die resultierende Ausgabe bereitgestellt wird, sei es eine durch Kommas getrennte Liste, ein Array, eine an STDOUT ausgegebene Liste usw. Das einzige Kriterium, das ich in Bezug auf die Ausgabe hervorheben muss, ist, dass sie sortiert werden muss .
  • Dies ist Code Golf, minimale Bytes erhalten maximale Pracht.
  • Wir werden dumme Schlupflöcher nicht tolerieren
WallyWest
quelle
1
Muss die Ausgabe sortiert werden?
Dennis
Hallo @Dennis, ja, ich habe vergessen zu erwähnen, dass ... die Ausgabe sortiert werden muss. Ich habe die Regeln entsprechend aktualisiert.
WallyWest
2
Müssen wir den Fall behandeln 0 0?
ETHproductions
@ETHproductions Ich habe das oben erwähnt 0 <= X + Y <= 16, also ja, weil 0 0dies als gültige Eingabe angesehen wird, die diese Regel erfüllt.
WallyWest
2
Wofür wird in diesem Fall die Ausgabe erwartet 0 0? Die Zahl 0 kann durch Null, eine oder mehrere Nullen dargestellt werden.
Dennis

Antworten:

5

Gelee , 8 Bytes

0,1xŒ!ḄQ

Probieren Sie es online!

Wie es funktioniert

0,1xŒ!ḄQ Main link. Argument: [x, y]

0,1x     Repeat 0 x times and 1 y times.
    Œ!   Compute all permutations of the result.
      Ḅ   Unbinary; convert each permutation from base 2 to integer.
       Q  Unique; deduplicate the results.
Dennis
quelle
Das ist ziemlich beeindruckend ... Gibt es auf dem allgemeinen Programmiermarkt viel Nachfrage nach J? Mir ist aufgefallen, dass Jelly darauf basiert?
WallyWest
1
Es hat eine Benutzerbasis in einigen spezifischen Anwendungen (hauptsächlich Mathematik / Statistik), aber ich weiß es ehrlich gesagt nicht. Ich habe J nicht außerhalb von Code Golf verwendet.
Dennis
@WallyWest Es wird nicht oft gefordert, da es sich am besten für eine Umgebung eignet, die von funktionaler Programmierung profitieren würde. In der Regel nur für sehr spezialisierte Programmierung.
Conor O'Brien
7

Python, 60 Bytes

lambda x,y:[n for n in range(1<<x+y)if bin(n).count('1')==y]

Teste es auf Ideone .

Wie es funktioniert

Alle positiven Zahlen, die binär mit x Nullen und y Einsen dargestellt werden können, sind deutlich kleiner als 2 x + y , da die kanonische binäre Darstellung der letzteren x + y + 1 Ziffern hat.

Das Lambda einfach iteriert über die ganzen Zahlen in [0, 2 x + y ) und hält alle ganzen Zahlen n in diesem Bereich, haben y diejenigen. Da n <2 x + y ist, kann mit x (oder weniger) Nullen dargestellt werden.

Dennis
quelle
5

Mathematica, 59 57 Bytes

Ein übliches Ergebnis mit Mathematica: Übergeordnete Funktionen = gut, lange Funktionsnamen = schlecht.

#+##&~Fold~#&/@Permutations@Join[0&~Array~#,1&~Array~#2]&

Join[0&~Array~#,1&~Array~#2]erstellt eine Liste mit der richtigen Anzahl von 0s und 1s. Permutationsgeneriert alle Permutationen dieser Liste, ohne Wiederholungen (wie ich gelernt habe) und in sortierter Reihenfolge. #+##&~Fold~#(eine golfuscated Version von #~FromDigits~2) konvertiert eine Liste von Basis-2-Ziffern in die Ganzzahl, die sie darstellen.

Vorherige Version vor Martin Enders Kommentar:

#~FromDigits~2&/@Permutations@Join[0&~Array~#,1&~Array~#2]&
Greg Martin
quelle
1
Trotzdem gut beobachtet und dokumentiert ... Mathematica ist großartig für das
Knacken von
1
FromDigitskann in der Regel gekürzt werden:#+##&~Fold~#&/@Permutations...
Martin Ender
@ MartinEnder: Ich verstehe! und sehen, wie man auch auf andere Basen verallgemeinert. Vielen Dank, dass Sie mir diese clevere Sprache beigebracht haben.
Greg Martin
1
Credits dafür gehen an alephalpha . ;)
Martin Ender
1
Es stellt sich heraus, dass der Wechsel zu Dennis 'Ansatz kürzer ist:Select[Range[2^+##]-1,x=#;DigitCount[#,2,1]==x&]&
Martin Ender,
5

CJam ( 15 bis 14 Bytes)

{As.*s:~e!2fb}

Dies ist ein anonymer Block (eine Funktion), der Eingaben als Array akzeptiert [number-of-ones number-of-zeros] und Ausgaben als Array zurückgibt.

Online-Demo


Weit weg von der Marke, aber interessanter : Dies ist ohne Permutation Builtins oder Basiskonvertierung:

{2\f#~1$*:X;[({___~)&_2$+@1$^4/@/|_X<}g;]}

Es würde gut funktionieren, wenn sich ein GolfScript entfalten würde.

Peter Taylor
quelle
Ich habe versucht, das ee{)*}/durch etwas zu ersetzen , indem ich .*diese 14-Byte-Lösung verwendet habe: {As.*s:~e!2fb}Die s:~sieht jetzt allerdings ein bisschen ineffizient aus.
Martin Ender
1
@MartinEnder, eigentlich habe ich damit angefangen .*und festgestellt, dass eedas schöner ist als zB 2,:a.*e_. Ich wusste jedoch nicht, dass dies e!unabhängig von der Reihenfolge der Argumente zu derselben Ausgabe führt.
Peter Taylor
Ja, das habe ich erst neulich selbst entdeckt.
Martin Ender
4

Japt , 16 Bytes

'0pU +'1pV)á mn2

Online testen!

Wie es funktioniert

                  // Implicit: U = first integer, V = second integer
'0pU              // Repeat the string "0" U times.
     +'1pV)       // Concatenate with the string "1" repeated V times.
           á      // Take all unique permutations.
             mn2  // Interpret each item in the resulting array as a binary number.
                  // Implicit: output last expression

Alternative Version, 17 Byte

2pU+V o f_¤è'1 ¥V
                   // Implicit: U = first integer, V = second integer
2pU+V              // Take 2 to the power of U + V.
      o            // Create the range [0, 2^(U+V)).
        f_         // Filter to only items where
           è'1     //  the number of "1"s in
          ¤        //  its binary representation
               ¥V  //  is equal to V. 
                   // Implicit: output last expression

Ich habe versucht, beide Versionen weiter zu golfen, aber ich kann einfach keinen Durchhang finden ...

ETHproductions
quelle
Das sieht toll aus ... und es funktioniert super! Der Dolmetscher zeigt jedoch nicht den transpilierten Code auf der rechten Seite an? Ich würde gerne sehen, wie es rendert?
WallyWest
@WallyWest Es transpiliert ungefähr zu ("0".p(U)+"1".p(V)).á().m("n",2); Jede der .x()Funktionen ist in der Quelldatei definiert .
ETHproductions
3

Ruby, 63 Bytes

Eine einfache Implementierung. Golfvorschläge sind willkommen.

->a,b{(?0*a+?1*b).chars.permutation.map{|b|(b*'').to_i 2}.uniq}

Ungolfing

def f(a,b)
  str = "0"*a+"1"*b                   # make the string of 0s and 1s
  all_perms = str.chars.permutation   # generate all permutations of the 0s and 1s
  result = []
  all_perms.do each |bin|             # map over all of the permutations
    bin = bin * ''                    # join bin together
    result << bin.to_i(2)             # convert to decimal and append
  end
  return result.uniq                  # uniquify the result and return
end
Sherlock9
quelle
3

Pyth - 11 Bytes

{iR2.psmVU2

Test Suite .

{                Uniquify
 iR2             Map i2, which converts from binary to decimal
  .p             All permutations
   s             Concatenate list
    mV           Vectorized map, which in this case is repeat
     U2          0, 1
     (Q)         Implicit input
Maltysen
quelle
2

Python 2 - 105 99 Bytes

+8 Byte, da unsere Ausgabe sortiert werden muss

lambda x,y:sorted(set(int("".join(z),2)for z in __import__('itertools').permutations("0"*x+"1"*y)))
Jeremy
quelle
Beeindruckende Bearbeitung!
WallyWest
1
Danke, ich hatte keine Ahnung, dass Sie Module in Lambda-Funktionen importieren können.
Jeremy
Ich habe immer gedacht, dass Sie für Code-Golf eine separate Import-Anweisung haben dürfen. (Natürlich müssen Sie immer noch die Länge angeben.) Dadurch sparen Sie möglicherweise ein oder zwei Bytes?
Neil
2

Mathematica, 47 Bytes

Cases[Range[2^+##]-1,x_/;DigitCount[x,2,1]==#]&

Eine unbenannte Funktion mit zwei Argumenten: Anzahl von 1s, Anzahl von 0s.

Im Wesentlichen eine Portierung von Dennis 'Python-Lösung . Wir erstellen einen Bereich von 0bis und behalten dann nur die Zahlen bei, deren Anzahl der Bits der ersten Eingabe entspricht. Das interessanteste Bit ist wahrscheinlich das, das Sequenzmagie verwendet , um die Klammern um das Hinzufügen der beiden Argumente zu vermeiden.2x+y-112^+##

Martin Ender
quelle
2

MATLAB 57 + 6

@(a,b)unique(perms([ones(1,a) zeros(1,b)])*2.^(0:a+b-1)')

laufen mit

ans(2,3)

ungolfed

function decimalPerms( nZeros, nOnes )
  a = [ones(1,nOnes) zeros(1,nZeros)];  % make 1 by n array of ones and zeros
  a = perms(a);                         % get permutations of the above 
  powOfTwo = 2.^(0:nOnes+nZeros-1)';    % powers of two as vector
  a = a * powOfTwo;                     % matrix multiply to get the possible values
  a = unique(a)                         % select the unique values and print
Richard
quelle
1
Wofür sind die plus 6 Bytes?
mbomb007
Ich wollte dasselbe fragen
WallyWest
2

MATL , 9 Bytes

y+:<Y@XBu

Probieren Sie es online!

Erläuterung

Der Ansatz ähnelt dem in Dennis 'Jelly-Antwort .

y     % Implicitly take two inputs (say 3, 2). Duplicate the first.
      %   STACK: 3, 2, 3
+     % Add
      %   STACK: 3, 5
:     % Range
      %   STACK: 3, [1 2 3 4 5]
<     % Less  than
      %   STACK: [0 0 0 1 1]
Y@    % All permutations
      %   STACK: [0 0 0 1 1; 0 0 0 1 1; ...; 0 0 1 0 1; ...; 1 1 0 0 0]
XB    % Binary to decimal
      %   STACK: [3 3 ... 5 ... 24]
u     % Unique
      %   STACK: [3 5 ... 24]
      % Implicitly display
Luis Mendo
quelle
1

Eigentlich 21 Bytes

Ein Port meiner Ruby-Antwort . Golfvorschläge sind willkommen. Probieren Sie es online!

│+)'1*@'0*+╨`εj2@¿`M╔

Wie es funktioniert

          Implicit input of a and b.
│+)       Duplicate a and b, add, and rotate to bottom of stack. Stack: [b a a+b]
'1*@      "1" times b and swap with a.
'0*+      "0" times a and add to get "0"*a+"1"*b.
╨`...`M   Take all the (a+b)-length permutations of "0"*a+"1"*b
          and map the following function over them.
  εj        Join the permutation into one string
  2@¿       Convert from binary to decimal
╔         Uniquify the resulting list and implicit return.
Sherlock9
quelle
1

Groovy 74 Bytes, 93 Bytes oder 123 Bytes

Ich weiß nicht, welches Ihrer Meinung nach die Frage ausführlicher beantwortet, aber ...

74 Byte Lösung

​{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().unique()}(1,2)

Bei einer Eingabe von 1,2 erhalten Sie:

[[1,0,1], [0,1,1], [1,1,0]]

93 Byte Lösung

{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().collect{it.join()}.unique()}(1,2)​

Bei einer Eingabe von 1,2 erhalten Sie:

[101, 011, 110]

123 Byte Lösung

{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().collect{it.join()}.unique().collect{Integer.parseInt(it,2)}}(1,2)

Bei einer Eingabe von 1,2 erhalten Sie:

[5, 3, 6]

Probieren Sie es hier aus:

https://groovyconsole.appspot.com/edit/5143619413475328

Magic Octopus Urn
quelle
Ich würde die 123-Byte-Lösung zählen, da diese dem in der Beschreibung erwähnten Ausgabetyp entspricht. Gut gemacht.
WallyWest
1

JavaScript (Firefox 48), 85 76 74 71 70 Bytes

3 Bytes dank @Neil gespart.

(m,n,g=x=>x?g(x>>1)-x%2:n)=>[for(i of Array(1<<m+n).keys())if(!g(i))i]

Das Array-Verständnis ist fantastisch. Schade, dass sie es noch nicht in die offizielle ECMAScript-Spezifikation geschafft haben.

JavaScript (ES6), 109 87 79 78 71 70 Byte

(m,n,g=x=>x?g(x>>1)-x%2:n)=>[...Array(1<<m+n).keys()].filter(x=>!g(x))

Sollte jetzt in allen ES6-kompatiblen Browsern funktionieren. 7 Bytes auf diesem gespeichert, auch dank @Neil.

ETHproductions
quelle
Äh, @ETHProductions, aus irgendeinem Grund bekomme ich es undefinedjetzt mit jedem Testlauf zurück, den ich mache ...?
WallyWest
@WallyWest Vergewissern Sie sich, dass Sie es zuerst einer Variablen zuweisen, z. B. f=(m,n)=>...und rufen Sie es dann wie folgt auf f(3,2). Wenn Sie das tun, welchen Browser verwenden Sie?
ETHproductions
Chrome 52 ... Ich habe keinen Firefox auf diesem Computer, daher konnte ich nur die Nicht-Firefox-Version von ES6 testen ...
WallyWest,
Versucht, es in der Browserkonsole auszuführen.
WallyWest
Oh, hmm. Ich sehe das Problem auch in Chrome. Versuchen Sie diese eval-lose Version (macht genau das gleiche, aber 3 Bytes länger):(m,n)=>{a="";for(i=0;i<1<<m+n;i++)if(i.toString(2).split(1).length==n+1)a+=i+" ";return a}
ETHproductions
1

Groovy 80 Bytes

basierend auf der Antwort von @carusocomputing

Seine 123-Byte-Lösung kann auf 80 Byte komprimiert werden:

80 Byte Lösung

{a,b->([0]*a+[1]*b).permutations()*.join().collect{Integer.parseInt(it,2)}}(1,2)

Bei einer Eingabe von 1,2 erhalten Sie:

[5, 3, 6]
norganos
quelle
1

C (GCC) , 72 68 Bytes

f(a,b){for(a=1<<a+b;a--;)__builtin_popcount(a)^b||printf("%d\n",a);}

Probieren Sie es online!

Leider gibt es kein popcount () in der Standardbibliothek, aber es wird von GCC als "eingebaute Funktion" bereitgestellt. Die Ausgabe ist sortiert, jedoch in umgekehrter Reihenfolge.

Vielen Dank an @ceilingcat für das Abschneiden von 4 Bytes!

G. Sliepen
quelle
Immer noch akzeptabel. Gute Arbeit!
WallyWest
0

PHP, 80 oder 63 Bytes

je nachdem , ob ich verwenden muss $argvoder kann verwendet werden $xund$y stattdessen.

for($i=1<<array_sum($argv);$i--;)echo$argv[2]-substr_count(decbin($i),1)?_:$i._;

druckt alle übereinstimmenden Nummern in absteigender Reihenfolge, die durch Unterstriche getrennt sind.
Dateiname darf nicht mit einer Ziffer beginnen.

Keine Builtins, 88 oder 71 Bytes

for($i=1<<array_sum($argv);$i--;print$c?_:$i._)for($n=$i,$c=$argv[2];$n;$n>>=1)$c-=$n&1;

Fügen Sie jeweils ein Byte für nur einen Unterstrich nach jeder Zahl hinzu.

@WallyWest: Sie hatten recht. Spart 3 Bytes für mich ausfor($i=-1;++$i<...;)

Titus
quelle
0

Perl 6 ,  64 62  49 Bytes

{(0 x$^a~1 x$^b).comb.permutations.map({:2(.join)}).sort.squish}
{[~](0,1 Zx@_).comb.permutations.map({:2(.join)}).sort.squish}
{(^2**($^x+$^y)).grep:{.base(2).comb('1')==$y}}

Erläuterung:

# bare block lambda with two placeholder parameters 「$^x」 and 「$^y」
{
  # Range of possible values
  # from 0 up to and excluding 2 to the power of $x+$y
  ( ^ 2 ** ( $^x + $^y ) )

  # find only those which
  .grep:

  # bare block lambda with implicit parameter of 「$_」
  {

    # convert to base 2
    # ( implicit method call on 「$_」 )
    .base(2)

    # get a list of 1s
    .comb('1')

    # is the number of elements the same
    ==

    # as the second argument to the outer block
    $y
  }
}
say {(0..2**($^x+$^y)).grep:{.base(2).comb('1')==$y}}(3,2)
# (3 5 6 9 10 12 17 18 20 24)
Brad Gilbert b2gills
quelle