Nombre de sous-séquences distinctes non vides d'expansion binaire

19

Une sous-séquence est une séquence que vous pouvez obtenir d'une autre en supprimant n'importe quelle quantité de caractères. Les non-vides séquences distinctes 100sont 0, 1, 00, 10, 100. Les non-vides séquences distinctes 1010sont 0, 1, 00, 01, 10, 11, 010, 100, 101, 110, 1010.

Écrivez un programme ou une fonction qui, étant donné un entier positif n, renvoie le nombre de sous-séquences distinctes non vides de l'expansion binaire de n .

Exemple: puisque 4est 100en binaire, et nous avons vu qu'il avait cinq sous-séquences distinctes non vides ci-dessus, donc f(4) = 5. À partir de n = 1 , la séquence commence:

1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12

Cependant, votre programme doit fonctionner pour tout n <2 50 en moins d'une seconde sur n'importe quelle machine moderne. Quelques grands exemples:

f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
code-golf combinatorics binary subsequence restricted-time orlp
la source
4
Je ne suis pas d'accord avec la restriction de temps.
ATaco
1
Cela semblait vraiment familier, surtout après avoir regardé l'intrigue. Il s'avère que j'ai examiné une séquence très étroitement liée plus tôt cette année, mais j'ai compté le nombre de nombres binaires distincts, pas de chaînes binaires, que vous obtenez lorsque vous prenez des sous-séquences (j'ai donc actualisé les zéros non significatifs). Je l'avais même mis en bac à sable, mais en raison de l'équivalence dans le post Math.SE, cela aurait été une dupe d'un défi Stern-Brocot. L'intrigue de votre séquence est cependant un peu plus agréable (c'est-à-dire plus chaotique). :)
Martin Ender
5
@ATaco La restriction de temps a une bonne raison. Il existe un algorithme efficace et il est intéressant mais bien jouable au golf. Si je n'ai pas de restriction de temps, je pense que presque toutes les réponses ne feraient que forcer brutalement toutes les sous-séquences possibles, ce qui ne fonctionnerait très, très rapidement plus. Dans un sens, ce sont des non-réponses.
orlp

Réponses:

10

Python 3 , 95 octets 83 octets

[-12 octets grâce à Mr.XCoder :)]

def f(x):
 v=[2,1];c=1
 for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
 return c

Essayez-le en ligne!

Une note sur l'algorithme. L'algorithme calcule l'incrément en sous-séquences uniques données par le bit à une position donnée t. L'incrément pour le premier bit est toujours 1. L'algorithme parcourt ensuite la séquence de bits s (t) et ajoute l'incrément v [s (t)]. À chaque étape, l'incrément pour le complément de s (t), v [1 - s (t)] est mis à jour à v [1] + v [0]. Le nombre final est la somme de tous les incréments.

Il doit s'exécuter dans O (log2 (n)), où n est le numéro d'entrée.

NofP
la source
1
83 octets ou 83 octets
M. Xcoder
8

JavaScript (ES6), 53 51 octets

f=(n,r=~(a=[]))=>n<1?~r:f(n/2,r*2-~~a[n&=1],a[n]=r)

Cas de test

Afficher l'extrait de code

Formaté et commenté

f = (                      // f is a recursive function taking:
  n,                       //   n = integer
  r = ~(                   //   r = last result, initially set to -1
    a = []                 //   and using a[] = last results for 0 and 1,
  )                        //   implicitly initialized to [0, 0]
) =>                       //
  n < 1 ?                  // if n is less than 1:
    ~r                     //   we're done: return -(r + 1)
  :                        // else:
    f(                     //   do a recursive call with:
      n / 2,               //     n / 2
      r * 2 - ~~a[n &= 1], //     updated result = r * 2 - last result for this binary digit
      a[n] = r             //     update last result for this binary digit
    )                      //   end of recursive call

Version non récursive, 63 octets

Enregistré 3 octets grâce à @ThePirateBay

s=>[...s.toString(2)].map(l=c=>l[p=r,r=r*2-~~l[c],c]=p,r=1)|r-1

Cas de test

Afficher l'extrait de code

Arnauld
la source
Je pense que vous pouvez économiser 3 octets en affectant la fonction interne (le premier argument de map) à la variable indicateur lau lieu d'un tableau vide.
@ThePirateBay Nice one. Merci!
Arnauld
7

Python 2 , 56 octets

f=lambda x,a=1,b=1:x and f(x/2,a+~x%2*b,x%2*a+b)or a+b-2

Essayez-le en ligne!

Reprenant la méthode de NofP .

59 octets de manière itérative:

x=input()
v=[1,1]
while x:v[x%2]=sum(v);x/=2
print sum(v)-2

Essayez-le en ligne!

xnor
la source
bel algorithme. Pourriez-vous ajouter une courte explication sur la raison pour laquelle cela fonctionne?
Jonah
6

Gelée , 10 octets

B3;BSṛ¦/’S

Cela utilise l'amélioration de @ xnor sur l'algorithme de @ NofP .

Essayez-le en ligne!

Contexte

Soit (a 1 , ..., a n ) une suite binaire finie. Pour chaque entier non négatif k ≤ n , définissez o k comme le nombre de sous-séquences uniques de (a 1 , ..., a k ) qui sont soit vides soit terminées en 1 , z k comme le nombre de sous-séquences uniques qui sont vide ou se termine par 0 .

Clairement, o 0 = z 0 = 1 , car la seule sous-séquence de la séquence vide est la séquence vide.

Pour chaque indice k , le nombre total de sous-séquences de (a 1 , ..., a k ) est o k + z k - 1 (la soustraction de 1 tient compte du fait que o k et z k comptent la séquence vide). Le nombre total de sous- séquences non vides est donc o k + z k - 2 . Le défi demande de calculer o n + z n - 2 .

N'importe quand k> 0 , nous pouvons calculer o k et z k récursivement. Il y a deux cas:

  • a k = 1

    z k = z k-1 , puisque (a 1 , ..., a k-1 ) et (a 1 , ..., a k-1 , 1) ont les mêmes sous-séquences se terminant par 0 .

    Pour chacune des o k - 1 sous-séquences non vides de (a 1 , ..., a k ) qui se terminent par 1 , nous pouvons supprimer le 1 de fin pour obtenir l'une des o k-1 + z k-1 - 1 sous- séquences (a 1 , ..., a k-1 ) . Inversement, l'ajout d'un 1 à chacune de ces dernières séquences o k-1 + z k-1 - 1 donne l'une des premières séquences o k - 1 . Ainsi, o k - 1 = o k-1 + zk-1 - 1 et o k = o k-1 + z k-1 .

  • un k = 0

    De façon similaire au cas précédent, on obtient les formules récursives o k = o k-1 et z k = z k-1 + o k-1 .

Comment ça fonctionne

B3;BSṛ¦/’S  Main link. Argument: n (positive integer)

B           Binary; convert n to base 2.
 3;         Prepend a 3.
   B        Binary; convert all integers in the resulting array to base 2, mapping
            0 to [0], 1 to [1], and the prepended 3 to [1, 1].
       /    Reduce the resulting array by the quicklink to the left, which will be 
            called with left argument [x, y] (integer pair) and right argument [j] 
            (either [0] or [1]).
      ¦     Sparse application.
    S           Compute the sum (x + y) and...
     ṛ          for each index in the right argument (i.e., for j)...
            replace the element of [x, y] at that index with (x + y).
       ’    Decrement both integers in the resulting pair.
        S   Take the sum.
Dennis
la source
hé dennis, cela vous dérangerait-il d'ajouter une courte explication sur les raisons pour lesquelles l'algorithme fonctionne?
Jonah
J'ai ajouté une explication.
Dennis
4

05AB1E , 12 octets

0¸sbvDO>yǝ}O

Essayez-le en ligne! Explication: Comme indiqué par les autres réponses, le nombre de sous-séquences pour une chaîne binaire a..y0qui se terminent par 1 est le même que le nombre pour la chaîne binaire a..y, tandis que le nombre qui se termine par a 0est le nombre total de sous-séquences pour le binaire chaîne a..y(qui chacun gagne un 0suffixe) plus une pour 0elle-même. Contrairement aux autres réponses, je n'inclus pas la sous-séquence vide car cela enregistre un octet construisant l'état initial.

0¸s             Push [0] under the input
   b            Convert the input to binary
    v     }     Loop over the digits
     D          Duplicate the array
      O         Take the sum
       >        Increment
        yǝ      Replace the index corresponding to the binary digit
           O    Take the sum of the final array
Neil
la source
1

Java 8, 97 octets

n->f(n,1,1)long f(long n,long a,long b){return n>0?f(n/2,a+Math.floorMod(~n,2)*b,n%2*a+b):a+b-2;}

Port de la réponse Python 2 de @xnor , qui à son tour est une amélioration de la réponse Python 3 de @NofP .

Essayez-le ici.

C'est peut-être une bonne chose que la balise à temps limité était présente, car j'avais initialement les éléments suivants pour forcer toutes les sous-séquences:

import java.util.*;n->p(n.toString(n,2)).size()-1;Set p(String s){Set r=new HashSet();r.add("");if(s.isEmpty())return r;Set q=p(s.substring(1));r.addAll(q);for(Object o:q)r.add(""+s.charAt(0)+o);return r;}

Essayez-le ici.

Ce qui a également fonctionné, mais a pris beaucoup trop de temps pour les trois derniers cas de test. Sans parler de sa longueur ( 208 204 octets ).

Kevin Cruijssen
la source
1

6502 code machine (C64), 321 octets

00 C0 20 FD AE A2 00 9D 4F C1 E8 20 73 00 90 F7 9D 4F C1 A0 FF C8 B9 4F C1 D0
FA A2 15 CA 88 30 0A B9 4F C1 29 0F 9D 4F C1 10 F2 A9 00 9D 4F C1 CA 10 F8 A9
00 A0 07 99 64 C1 88 10 FA A0 40 A2 6C 18 BD E4 C0 90 02 09 10 4A 9D E4 C0 E8
10 F2 A2 07 7E 64 C1 CA 10 FA 88 F0 13 A2 13 BD 50 C1 C9 08 30 05 E9 03 9D 50
C1 CA 10 F1 30 D1 A2 0F A9 00 9D 3F C1 CA D0 FA A9 01 8D 3F C1 8D 47 C1 A2 08
CA BD 64 C1 F0 FA A0 09 1E 64 C1 88 90 FA B0 0A CA 30 28 A0 08 1E 64 C1 90 04
A9 47 B0 02 A9 4F 8D AF C0 86 FE A2 F8 18 BD 47 C0 7D 4F C0 9D 47 C0 E8 D0 F4
A6 FE 88 D0 DC F0 D5 A2 F8 BD 47 C0 7D 4F C0 9D 6C C0 E8 D0 F4 AD 64 C1 E9 01
8D 64 C1 A2 F9 BD 6C C0 E9 00 9D 6C C0 E8 D0 F5 A0 15 A9 00 99 4E C1 88 D0 FA
A0 40 A2 13 BD 50 C1 C9 05 30 05 69 02 9D 50 C1 CA 10 F1 0E 64 C1 A2 F9 3E 6C
C0 E8 D0 FA A2 13 BD 50 C1 2A C9 10 29 0F 9D 50 C1 CA 10 F2 88 D0 D1 E0 14 F0
06 E8 BD 4F C1 F0 F6 09 30 99 4F C1 C8 E8 E0 15 F0 05 BD 4F C1 90 F0 A9 00 99
4F C1 A9 4F A0 C1 4C 1E AB

Démo en ligne

Démo en ligne avec vérification des erreurs (346 octets)

Utilisation:, sys49152,[n] par exemple sys49152,911188917558917.

La restriction de temps et les cas de test nécessitent des solutions pour calculer en nombres 64 bits, donc le temps de prouver que le C64 est qualifié de " machine moderne ";)

Bien sûr, cela nécessite un peu de code, le système d'exploitation ne fournit rien pour les entiers supérieurs à 16 bits. La partie boiteuse ici: c'est encore une autre implémentation (légèrement modifiée) de l'algorithme de NofP resp. Variante améliorée de xnor . Merci pour l'idée;)

Explication

Voici une liste commentée de démontage de la partie pertinente faisant l'algorithme:

.C:c06c  A2 0F       LDX #$0F           ; 15 bytes to clear
.C:c06e  A9 00       LDA #$00
.C:c070   .clearloop:
.C:c070  9D 3F C1    STA .num_a,X
.C:c073  CA          DEX
.C:c074  D0 FA       BNE .clearloop
.C:c076  A9 01       LDA #$01           ; initialize num_a and num_b
.C:c078  8D 3F C1    STA .num_a         ; to 1
.C:c07b  8D 47 C1    STA .num_b
.C:c07e  A2 08       LDX #$08           ; 8 bytes of input to check,
.C:c080   .findmsb:                     ; start at most significant
.C:c080  CA          DEX
.C:c081  BD 64 C1    LDA .nc_num,X
.C:c084  F0 FA       BEQ .findmsb       ; repeat until non-0 byte found
.C:c086  A0 09       LDY #$09           ; 8 bits to check (+1 for pre dec)
.C:c088   .findbit:
.C:c088  1E 64 C1    ASL .nc_num,X      ; shift left, highest bit to carry
.C:c08b  88          DEY
.C:c08c  90 FA       BCC .findbit       ; bit was zero -> repeat
.C:c08e  B0 0A       BCS .loopentry     ; jump into calculation loop
.C:c090   .mainloop:
.C:c090  CA          DEX                ; next byte
.C:c091  30 28       BMI .done          ; index -1? -> done calculating
.C:c093  A0 08       LDY #$08           ; 8 bits to check
.C:c095   .bitloop:
.C:c095  1E 64 C1    ASL .nc_num,X      ; shift left, highest bit to carry
.C:c098  90 04       BCC .tgt_b         ; if 0, store addition result in num_b
.C:c09a   .loopentry:
.C:c09a  A9 47       LDA #$47
.C:c09c  B0 02       BCS .tgt_a         ; ... else store in num_a ...
.C:c09e   .tgt_b:
.C:c09e  A9 4F       LDA #$4F
.C:c0a0   .tgt_a:
.C:c0a0  8D AF C0    STA $C0AF          ; ... using self-modification.
.C:c0a3  86 FE       STX $FE            ; save byte index
.C:c0a5  A2 F8       LDX #$F8           ; index for adding
.C:c0a7  18          CLC
.C:c0a8   .addloop:
.C:c0a8  BD 47 C0    LDA $C047,X        ; load byte from num_a
.C:c0ab  7D 4F C0    ADC $C04F,X        ; add byte from num_b
.C:c0ae  9D 47 C0    STA $C047,X        ; store to num_a or num_b
.C:c0b1  E8          INX                ; next index
.C:c0b2  D0 F4       BNE .addloop       ; done if index overflown
.C:c0b4  A6 FE       LDX $FE            ; restore byte index
.C:c0b6  88          DEY                ; decrement bit index
.C:c0b7  D0 DC       BNE .bitloop       ; bits left in current byte -> repeat
.C:c0b9  F0 D5       BEQ .mainloop      ; else repeat main loop
.C:c0bb   .done:
.C:c0bb  A2 F8       LDX #$F8           ; index for adding
.C:c0bd   .addloop2:
.C:c0bd  BD 47 C0    LDA $C047,X        ; load byte from num_a
.C:c0c0  7D 4F C0    ADC $C04F,X        ; add byte from num_b
.C:c0c3  9D 6C C0    STA $C06C,X        ; store to nc_num (result)
.C:c0c6  E8          INX                ; next index
.C:c0c7  D0 F4       BNE .addloop2      ; done if index overflown
.C:c0c9  AD 64 C1    LDA .nc_num        ; load least significant result byte
.C:c0cc  E9 01       SBC #$01           ; subtract 2 (1 + negated carry)
.C:c0ce  8D 64 C1    STA .nc_num        ; store least significant result byte
.C:c0d1  A2 F9       LDX #$F9           ; index for subtract
.C:c0d3   .subloop:
.C:c0d3  BD 6C C0    LDA $C06C,X        ; subtract 0 from all other bytes
.C:c0d6  E9 00       SBC #$00           ; for handling carry if necessary
.C:c0d8  9D 6C C0    STA $C06C,X
.C:c0db  E8          INX
.C:c0dc  D0 F5       BNE .subloop

Le reste est une entrée / sortie et une conversion entre une chaîne et un entier non signé 64 bits (little-endian) en utilisant un algorithme à double touche. Si vous êtes intéressé, voici la source complète de l'assemblage pour la version avec vérification des erreurs - la version "golfée" est dans la branche "golf".

Felix Palmen
la source