15
\$\begingroup\$

Given an alphabet represented as a nonempty set of positive integers, and a word made up of symbols from that alphabet, find that word's position in the lexicographically ordered set of all words, assuming words can't contain duplicate symbols.

Example

Consider the alphabet {1, 2, 3} and the word [2, 3, 1]. The set of all possible words, ordered via lexicographic order is

{
  [1],
  [1, 2],
  [1, 2, 3],
  [1, 3],
  [1, 3, 2],
  [2],
  [2, 1],
  [2, 1, 3],
  [2, 3],
  [2, 3, 1],
  [3],
  [3, 1],
  [3, 1, 2],
  [3, 2],
  [3, 2, 1]
}

[2, 3, 1] is the tenth element in the set, so the answer is 10 (9 if you use zero indexing).

Input/Output

Input can be taken in any reasonable format, including taking the alphabet as a sorted list, or taking the alphabet/word as a string.

Output can be zero or one indexed, please say which one you choose in your answer.

This is , so the shortest answer wins.

Testcases

One indexed:

alphabet, word -> location (1 indexed)
{1, 2, 3} , [] -> undefined
{1, 2, 3}, [1] -> 1
{1, 2, 3}, [3] -> 11
{1, 2, 3}, [2, 3, 1] -> 10
{1, 2, 3}, [3, 2, 1] -> 15
{1, 3, 4, 6}, [3, 1, 4] -> 19 
{1, 3, 4, 6}, [3, 1, 6, 4] -> 22
{1,3, 4, 16, 23, 37, 43, 57}, [37, 43, 16, 3] -> 79332
{41, 57, 60, 61, 71, 80, 113, 125, 131, 139, 141, 184, 197, 200, 201, 214, 215, 216, 223, 236, 238, 240, 244, 252, 264, 279, 300, 335, 340, 393, 410, 414, 421, 436, 441, 447, 461, 466, 483, 490, 525, 537, 540, 543, 547, 551, 552, 557, 569, 583, 584, 591, 593, 595, 596, 607, 610, 613, 614, 620, 621, 634, 637, 643, 652, 683, 691, 713, 726, 733, 738, 750, 757, 767, 777, 789, 803, 812, 813, 817, 844, 850, 856, 878, 901, 910, 926, 947, 949, 951, 953, 958, 962, 969, 982, 995}, [252, 300, 969, 844, 856, 713, 60, 621, 393, 637, 634, 441, 817, 264, 551, 757, 926, 240, 461, 421, 767, 726, 223, 610, 547, 141, 593, 184, 200, 643, 583, 614, 958, 540, 201, 214, 584, 591, 525, 652, 466, 414, 995, 125, 813, 951, 901, 215, 947, 410, 113, 279, 238, 57, 750, 607, 61, 131, 216, 340, 569, 803, 557, 878, 691, 80, 850, 483, 71, 613, 41, 244, 789, 595, 447, 596, 812, 543, 953, 620, 962, 436, 537, 733, 738, 197, 949, 982, 139, 683, 910, 236, 552, 490, 777, 335] -> 653513463887666116337968717018588523734749776398084200209718028326146195147009645472571018754197481757464478858415475671625444580437153140577102475638

Zero indexed:

alphabet, word -> location (0 indexed)
{1, 2, 3} , [] -> undefined
{1, 2, 3}, [1] -> 0
{1, 2, 3}, [3] -> 10
{1, 2, 3}, [2, 3, 1] -> 9
{1, 2, 3}, [3, 2, 1] -> 14
{1, 3, 4, 6}, [3, 1, 4] -> 18 
{1, 3, 4, 6}, [3, 1, 6, 4] -> 21
{1,3, 4, 16, 23, 37, 43, 57}, [37, 43, 16, 3] -> 79331
{41, 57, 60, 61, 71, 80, 113, 125, 131, 139, 141, 184, 197, 200, 201, 214, 215, 216, 223, 236, 238, 240, 244, 252, 264, 279, 300, 335, 340, 393, 410, 414, 421, 436, 441, 447, 461, 466, 483, 490, 525, 537, 540, 543, 547, 551, 552, 557, 569, 583, 584, 591, 593, 595, 596, 607, 610, 613, 614, 620, 621, 634, 637, 643, 652, 683, 691, 713, 726, 733, 738, 750, 757, 767, 777, 789, 803, 812, 813, 817, 844, 850, 856, 878, 901, 910, 926, 947, 949, 951, 953, 958, 962, 969, 982, 995}, [252, 300, 969, 844, 856, 713, 60, 621, 393, 637, 634, 441, 817, 264, 551, 757, 926, 240, 461, 421, 767, 726, 223, 610, 547, 141, 593, 184, 200, 643, 583, 614, 958, 540, 201, 214, 584, 591, 525, 652, 466, 414, 995, 125, 813, 951, 901, 215, 947, 410, 113, 279, 238, 57, 750, 607, 61, 131, 216, 340, 569, 803, 557, 878, 691, 80, 850, 483, 71, 613, 41, 244, 789, 595, 447, 596, 812, 543, 953, 620, 962, 436, 537, 733, 738, 197, 949, 982, 139, 683, 910, 236, 552, 490, 777, 335] -> 653513463887666116337968717018588523734749776398084200209718028326146195147009645472571018754197481757464478858415475671625444580437153140577102475637

Note: This challenge is loosely based upon an old weekly challenge on replit.

\$\endgroup\$
6
  • \$\begingroup\$ Are the exact numbers in the inputs important, or just that the word and alphabet match? For example, in the last case is it necessary that the input represents "995" as a character in the alphabet, or only that the alphabet has 95 characters and the word uses the correct ones? Or, to put it most directly, is it alright if the alphabet is a list of bytes instead of numbers? \$\endgroup\$ Oct 5 at 17:36
  • 1
    \$\begingroup\$ @KamilDrakari A list of bytes is just fine. After all, bytes are just small numbers- so long as you don't use that fact to trivialize the problem there is nothing wrong with using them. The key thing is that given a 95 character alphabet your answer should theoretically do the right thing, even if practical constraints like limited ram and the heat death of the universe get in the way. \$\endgroup\$
    – Aiden4
    Oct 5 at 17:47
  • 1
    \$\begingroup\$ It seems that the alphabet is always ordered naturally (i.e. a smaller integer always comes before a larger one) - is that guaranteed? (And if so, why not just use a prefix of the natural numbers rather than a sparse set?) \$\endgroup\$ Oct 5 at 17:56
  • \$\begingroup\$ @JonathanAllan taking in the alphabet as a sorted list or ordered set (like a b-tree set or something) is explicitly allowed. I went with the sparse set primarily because I thought it made a slightly more interesting question. \$\endgroup\$
    – Aiden4
    Oct 5 at 18:38
  • 2
    \$\begingroup\$ @Arnauld you don't have to support those cases. Undefined means any behavior is valid, feel free to do whatever's golfiest. \$\endgroup\$
    – Aiden4
    Oct 5 at 23:16

14 Answers 14

7
\$\begingroup\$

Python 3.8, 93 bytes

lambda a,w:sum(sum(map(e.__gt__,a:=a-{e}))*h(len(a))+1for e in w)
h=lambda n:n<1or 1+n*h(n-1)

An unamed function that accepts the alphabet, a, as a set and the word, w, as an Iterable and returns the 1-indexed index of the word (an empty word will give 0).

Try it online!

How?

We calculate the number of "blocks" in the set of valid words that we need to pass for each character in the word and multiply by the size of said "blocks", moving forward one more for each character.

The size of the block at each step is the number of words that may be formed from the alphabet once we've removed the current character and any previously processed characters. This is OEIS: A000522 and is calculated with the recursive helper function, h.

The number of blocks to pass at each step is the number of characters that come before the current character in the alphabet once we've removed any previously processed characters and is calculated with sum(map(e.__gt__,a:=a-{e})) which deals with removing the word character from the alphabet.

\$\endgroup\$
6
\$\begingroup\$

Vyxal, 5 bytes

Þxs?ḟ

Try it Online!

Explanation:

Þxs?ḟ
Þx    All possible combinations of the set (without replacements)
  s   Sort
   ?ḟ Output index of the word 
\$\endgroup\$
0
5
\$\begingroup\$

JavaScript (ES6), 73 bytes

Expects (word)(alphabet). The result is 1-indexed.

b=>g=(a,w=k=0)=>w==b||a.some((v,i)=>g(a.filter(_=>i--),w?w+[,v]:v),k++)*k

Try it online!

Commented

b =>              // outer function taking the word array b[]
g = (             // inner recursive function taking:
  a,              //   the alphabet array a[]
  w = k = 0       //   the current word w and the corresponding index k
) =>              //
w == b ||         // stop if w is equal to b (implicit string coercion)
a.some((v, i) =>  // otherwise, for each value v at position i in a[]:
  g(              //   do a recursive call:
    a.filter(_ => //     pass a copy of a[] with ...
      i--         //       ... the i-th entry removed
    ),            //
    w ?           //     if w is already initialized:
      w + [, v]   //       append a comma followed by v to w
    :             //     otherwise:
      v           //       set w to v
  ),              //   end of recursive call
  k++             //   before some() is actually processed: increment k
) * k             // end of some(); return k
\$\endgroup\$
4
\$\begingroup\$

Factor + math.combinatorics, 64 bytes

[ all-subsets [ <permutations> ] map concat natural-sort index ]

Try it online!

1-indexed. Takes input as word alphabet.

  • all-subsets get all subsets of the alphabet
  • [ <permutations> ] map concat get each permutation of each set and flatten it to a list
  • natural-sort sort
  • index find the index of the word
\$\endgroup\$
1
  • \$\begingroup\$ I'm a simple man. I see Factor I upvote. \$\endgroup\$
    – south
    Oct 6 at 3:00
2
\$\begingroup\$

Python, 101 bytes

f=lambda a,w:w>[]and sorted(a).index(w[0])*g(len(a))+f(a-{w[0]},w[1:])+1
g=lambda n:n and~-n*g(n-1)+1

Attempt This Online!

Does actually calculate the index. 1-based, 0 for undefined.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 62 57 bytes

->a,w{a.product(*a.map{a}).map(&:uniq).sort.uniq.index w}

Try it online!

Thanks Jordan for the hint that saved 5 bytes.

\$\endgroup\$
2
  • \$\begingroup\$ You don't need the *[...] around the arguments to product since you're already splatting [a]*a.size. 59 bytes. \$\endgroup\$
    – Jordan
    Oct 5 at 21:48
  • \$\begingroup\$ using |[] instead of #uniq saves one byte \$\endgroup\$
    – south
    Oct 6 at 2:56
1
\$\begingroup\$

Charcoal, 30 bytes

≔⟦υ⟧ζFζF⁻θι⊞ζ⁺ι⟦κ⟧W⁻ζυ⊞υ⌊ιI⌕υη

Try it online! Link is to verbose version of code. 1(!)-indexed. Explanation:

≔⟦υ⟧ζFζ

Start a breadth-first search for words with the empty word (this consumes index 0, which is why the output becomes 1-indexed.)

F⁻θι⊞ζ⁺ι⟦κ⟧

For each word, create new words by suffixing all symbols not already used.

W⁻ζυ⊞υ⌊ι

Sort the words lexicographically.

I⌕υη

Output the desired word's position.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 107 bytes

lambda a,b:sorted([[*p]for i in range(len(a))for p in permutations(a,i+1)]).index(b)
from itertools import*

Try it online!

Get permutations of all sizes, sort them and return index of required word.

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 67 bytes

f(a,w)=sum(l=1,#w,sum(i=0,k=#a=a[^1+n=#[1|b<-a,b<w[l]]],k!/i!)*n+1)

Attempt This Online!

Takes the alphabet as a sorted list. 1-indexed.

A port of Jonathan Allan's Python answer, but using the formula \$a(n)=\sum_{i=0}^n k!/i!\$ for OEIS A000522.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 8 bytes

xSs.pMyE

Test suite

Takes the word as a list as the first input and the alphabet as a list as the second input, outputs the 1-index of the word. Unfortunately hits a MemoryError / times out for that last one, but I can't think of a reason it shouldn't work in theory.

Explanation:

xSs.pMyE  | Full code
xSs.pMyEQ | with implicit variables
----------+-----------------------------------------
      yE  | Generate all subsets of alphabet
   .pM    | Generate all permutations of each subset
  s       | Flatten the list
 S        | Sort the list
x       Q | Find the index of the word
\$\endgroup\$
1
\$\begingroup\$

Japt, 10 8 bytes

à cá ÍbV

Try it

1-indexed output. Takes the alphabet as a sorted string with each symbol represented by a unique byte, then the word as another string.

à cá ÍbV 
à        # Get all substrings of the alphabet
   á     # Get all the permutations of each substring
  c      # Flatten to a single array
     Í   # Sort lexicographically by the alphabet
      bV # Find the index of the word

The last test case runs slow enough that I haven't been able to check its output, but alphabets of that length should be supported.

\$\endgroup\$
7
  • \$\begingroup\$ I can't say I'm familiar with japt, but couldn't you just not skip the empty string and output one indexed instead? It seems to work \$\endgroup\$
    – Aiden4
    Oct 5 at 20:51
  • \$\begingroup\$ @Aiden4 If I don't remove the empty string, then an empty input and any other invalid inputs would not all result in the same output; specifically, empty would become 0 and others would stay -1. If that's fine I can save that byte \$\endgroup\$ Oct 5 at 20:55
  • 2
    \$\begingroup\$ It doesn't matter what you do on invalid inputs, because they're invalid. Unless validating the input is part of the challenge, you may assume all input is valid. \$\endgroup\$
    – Aiden4
    Oct 5 at 21:10
  • \$\begingroup\$ It doesn't look to me like you need the U so you should be able to replace nU<space> with Í. \$\endgroup\$
    – Shaggy
    Oct 6 at 11:47
  • \$\begingroup\$ @Shaggy I don't know why that works but it does seem to. \$\endgroup\$ Oct 6 at 15:06
1
\$\begingroup\$

Nibbles, 9 8 bytes (16 nibbles)

?`<+.`_0$``p$
?`<>>+.`_0$``p$
       `_0$      # get all subsequences of arg1
      .          # and map over this
           ``p$  # getting all permutations of each list,
     +           # and flatten this list-of-list-of-lists,
   >>            # remove the first element (the empty list),
 `<              # and sort the list-of-lists,
?                # finally, get the index of arg2.            

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Haskell, 60 58 bytes

f l=do y<-l;(y:)<$>[]:f[x|x<-l,x/=y]
a!w=sum[1|x<-f a,w>x]

Try it online!

Thanks to @Laikoni for saving 2 Bytes using do notation.

  • 0 indexed

f l generates vocabulary of set l

a!w counts words less than w

\$\endgroup\$
1
  • \$\begingroup\$ -2 bytes by using do as concatMap: Try it online! \$\endgroup\$
    – Laikoni
    Nov 1 at 18:52
0
\$\begingroup\$

05AB1E, 9 bytes

œ€æ€`êÅΔQ

1-based indexing (or actually 0-based indexing, by also handling [] at index 0).

Try it online or verify (almost) all test cases (the last two test cases are omitted, because they time-out on TIO).

Explanation:

œ          # Get the powerset of the (implicit) input-list, including empty list
 ۾        # Get all permutations of each sublist
   €`      # Flatten it one level down
     ê     # Sorted-uniquify the inner lists lexicographically
      ÅΔ   # Get the first (0-based) index which is truthy for:
        Q  #  Is it equal to the second (implicit) input-list?
           # (which is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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