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.

Improve this question
\$\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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 at 23:16

14 Answers 14

Reset to default
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.

Improve this answer
\$\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
Improve this answer
\$\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
Improve this answer
\$\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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I'm a simple man. I see Factor I upvote. \$\endgroup\$ Commented Oct 6, 2022 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.

Improve this answer
\$\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.

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

Charcoal, 30 bytes

≔⟦υ⟧ζＦζＦ⁻θι⊞ζ⁺ι⟦κ⟧Ｗ⁻ζυ⊞υ⌊ιＩ⌕υη

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

≔⟦υ⟧ζＦζ

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

Ｆ⁻θι⊞ζ⁺ι⟦κ⟧

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

Ｗ⁻ζυ⊞υ⌊ι

Sort the words lexicographically.

Ｉ⌕υη

Output the desired word's position.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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
Improve this answer
\$\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.

Improve this answer
\$\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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 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\$ Commented Oct 5, 2022 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\$ Commented Oct 6, 2022 at 11:47
  • \$\begingroup\$ @Shaggy I don't know why that works but it does seem to. \$\endgroup\$ Commented Oct 6, 2022 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

Improve this answer
\$\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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ -2 bytes by using do as concatMap: Try it online! \$\endgroup\$ Commented Nov 1, 2022 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)
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.