Задавать слово, печатать свой индекс, слова могут быть соответственно увеличены

Ответ 1

• Сначала сделайте все буквы:
  • 'aez' станет 1,5,26
• Сделать эти переменные чисел называемыми... X3, X2, X1
  • 26 будет X1, 5 будет X2, 1 будет X3 (обратите внимание, справа налево)

Теперь для магической формулы:

Закодировано примерами и демонстрирует скорость даже в худшем случае:

def comb(n,k): #returns combinations
    p = 1 #product
    for i in range(k):
        p *= (n-i)/(i+1)
    return p

def solve(string):
    x = []
    for letter in string:
        x.append(ord(letter)-96)  #convert string to list of integers
    x = list(reversed(x))  #reverse the order of string
    #Next, the magic formula
    return x[0]+sum(comb(26,i)-comb(26-x[i-1]+1,i)*(1-i/(26-x[i-1]+1)) for i in range(2,len(x)+1))

solve('bhp')
764.0
>>> solve('afkp')
3996.0
>>> solve('abcdefghijklmnopqrstuvwxyz')
67108863.0
>>> solve('hpz')
2090.0
>>> solve('aez')
441.0
>>> if 1:
        s = ''
        for a in range(97,97+26):
                s += chr(a)
        t = time.time()
        for v in range(1000):
                temp = solve(s)
        print (time.time()-t)


0.1650087833404541

Чтобы понять мое объяснение этой формуле, мне нужно перейти к математическому вхождению в треугольник паскаля и теорему бинома:

Вот треугольник паскаля:

Переходя сверху справа налево, сначала есть последовательность из 1s. Затем последовательность счетных чисел. Следующая последовательность - это сумма чисел подсчета. Они известны как треугольные числа. Следующая последовательность представляет собой сумму треугольных чисел, называемых тетраэдрическими числами, и эта картина продолжается и продолжается.

Теперь для биномиальной теоремы:

Объединив биномиальную теорему и треугольник парабол, можно видеть, что n-е треугольное число:

и n-е тетраэдрическое число:

сумма первых n тетраэдрических чисел:

и далее...

Теперь для объяснения. Для этого объяснения я буду использовать только 6 букв, а-f и заменяю их цифрами 1-6. Процедура такая же, как и с другими буквами

Если длина равна 1, то возможные последовательности:

1
2
3
4
5
6

В этом ответе просто значение

Теперь для длины 2:

12  13  14  15  16
23  24  25  26
34  35  36
45  46
56

Чтобы решить эту проблему, мы разделим ее на 3 части:

• Найти общее количество элементов в строках выше
  • В этом случае в первой строке есть 5 элементов, 4 - во втором, 3 в третьем и так далее. Нам нужно найти способ суммирования первых n элементов последовательности (5,4,3,2,1). Для этого мы вычитаем треугольные числа. (1 + 2 + 3 + 4 + 5) - (1 + 2 + 3) = (4 + 5). Аналогично (1 + 2 + 3 + 4 + 5) - (1 + 2) = 3 + 4 + 5. Поэтому это значение равно:
• Теперь мы учли значения выше нашей цели и интересуемся только столбцом, в котором он находится. Чтобы найти это, добавим x1-x2
• Наконец, нам нужно добавить количество длин 1 последовательности. Это равно 6. Поэтому наша формула:

Далее мы повторим для последовательностей длины 3:

123  124  125  126
134  135  136
145  146
156

234  235  236
245  246
256

345  346
356

456

Мы снова разделим эту проблему на шаги:

• Найдите количество элементов над каждым массивом. Значения массивов - это треугольники с обратным треугольником (10, 6, 3, 1). На этот раз вместо вычитания треугольных чисел вычитаем тетраэдральные числа:
• Обратите внимание, как каждый отдельный массив имеет форму последовательности длиной 2. Вычитая x3 из x1 и x2, мы уменьшаем последовательность до степени 2. Например, мы вычитаем 2 из второго массива

Это

234  235  236
245  246
256

становится

12  13  14
23  24
34  

3. Теперь мы можем использовать формулу длины 2 с 6-x3 вместо 6, поскольку наши последовательности теперь имеют другое максимальное значение
4. Наконец, мы добавим общее число последовательностей длины 1 и длины 2. Оказывается, существует образец того, сколько последовательностей определенной длины есть. Ответ - это комбинации. Существуют последовательности длины 1, длины 2 и т.д.

Объединяя их, наша общая формула для длины 3 становится:

Мы можем следовать этой схеме редукции для более длинных последовательностей

Теперь мы выберем наши формулы для поиска шаблонов:

Длина 1: y1

Длина 2:

Длина 3:

Примечание. Я также использовал длину 4, чтобы убедиться, что удержанные шаблоны

С небольшим количеством математики, группировки терминов и изменением от 6 до 26 наша формула становится:

Чтобы упростить это, нужно сделать больше математики.
Это тождество справедливо для всех a и b. Для быстрого осуществления упражнений докажите это (не очень сложно):

Это тождество позволяет в дальнейшем группировать и отрицать термины для достижения нашей значительно упрощенной формулы:

Ответ 2

Это комбинация двух проблем: синтаксический анализ числа в базе, которая не равна 10 и определение, если вход сортируется.

Обратите внимание, что, поскольку это, вероятно, домашнее задание, вы, вероятно, не можете просто использовать существующие методы для выполнения тяжелой работы.

Ответ 3

Для букв этого мнимого алфавита длиной более одного символа мы можем использовать рекурсию:

XnXn-1..X1 = 
  max(n-1) 
      + (max(n-1) - last (n-1)-character letter before 
                    the first (n-1)-character letter after a)
  ... + (max(n-1) - last (n-1)-character letter before the
                    first (n-1)-character letter after the-letter-before-Xn)
  + 1 + ((Xn-1..X1) - first (n-1)-character letter after Xn)

where max(1) = z, max(2) = yz...

Код Haskell:

import Data.List (sort)
import qualified Data.MemoCombinators as M

firstAfter letter numChars = take numChars $ tail [letter..]

lastBefore letter numChars = [toEnum (fromEnum letter - 1) :: Char] 
                          ++ reverse (take (numChars - 1) ['z','y'..])

max' numChars = reverse (take numChars ['z','y'..])

loop letter numChars = 
  foldr (\a b -> b 
                 + index (max' numChars) 
                 - index (lastBefore (head $ firstAfter a numChars) numChars)
        ) 0 ['a'..letter]

index = M.list M.char index' where
  index' letter
    | null (drop 1 letter)  = fromEnum (head letter) - 96
    | letter /= sort letter = 0
    | otherwise = index (max' (len - 1))
                + loop (head $ lastBefore xn 1) (len - 1)
                + 1
                + index (tail letter) - index (firstAfter xn (len - 1))
   where len = length letter
         xn = head letter

Вывод:

*Main> index "abcde"
17902

*Main> index "abcdefghijklmnopqrstuvwxyz"
67108863
(0.39 secs, 77666880 bytes)

Ответ 4

Система нумерации базы 26. Я бы предложил вам посмотреть на восьмеричные, десятичные и шестнадцатеричные системы нумерации, как только вы поймете, как вычислить любое из них до десятичного, вы тоже это знаете.

Ответ 5

Это действительно должно быть комментарий, но я не могу поместить код в комментарий.

Я написал программу грубой силы для вычисления числа одного, двух, трех, четырех и пяти буквенных слов на основе критериев, предоставленных оригинальным плакатом.

Представьте себе такой алфавит слов, что последовательность символов в слове должна быть только в порядке возрастания.

Вот результаты моей программы.

One letter words   - 26
Two letter words   - 325
Three letter words - 2600
Four letter words  - 14950
Five letter words  - 65780

Total words        - 83681

Моим "решением" было бы создание словаря всех слов от a до abcdefghijklmnopqrstuvwxyz.

Вот код, который я использовал. Возможно, кто-то может посмотреть на вложенные петли и придумать формулу. Я не могу.

public class WordSequence implements Runnable {

    private int wordCount = 0;

    @Override
    public void run() {
        int count = createOneLetterWords();
        System.out.println("One letter words   - " + count);
        count = createTwoLetterWords();
        System.out.println("Two letter words   - " + count);
        count = createThreeLetterWords();
        System.out.println("Three letter words - " + count);
        count = createFourLetterWords();
        System.out.println("Four letter words  - " + count);
        count = createFiveLetterWords();
        System.out.println("Five letter words  - " + count);

        System.out.println("\nTotal words        - " + wordCount);
    }

    private int createOneLetterWords() {
        int count = 0;

        for (int i = 0; i < 26; i++) {
            createWord(i);
            wordCount++;
            count++;
        }
        return count;
    }

    private int createTwoLetterWords() {
        int count = 0;

        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                createWord(i, j);
                wordCount++;
                count++;
            }
        }
        return count;
    }

    private int createThreeLetterWords() {
        int count = 0;

        for (int i = 0; i < 24; i++) {
            for (int j = i + 1; j < 25; j++) {
                for (int k = j + 1; k < 26; k++) {
                    createWord(i, j, k);
                    wordCount++;
                    count++;
                }
            }
        }
        return count;
    }

    private int createFourLetterWords() {
        int count = 0;

        for (int i = 0; i < 23; i++) {
            for (int j = i + 1; j < 24; j++) {
                for (int k = j + 1; k < 25; k++) {
                    for (int m = k + 1; m < 26; m++) {
                        createWord(i, j, k, m);
                        wordCount++;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private int createFiveLetterWords() {
        int count = 0;

        for (int i = 0; i < 22; i++) {
            for (int j = i + 1; j < 23; j++) {
                for (int k = j + 1; k < 24; k++) {
                    for (int m = k + 1; m < 25; m++) {
                        for (int n = m + 1; n < 26; n++) {
                            createWord(i, j, k, m, n);
                            wordCount++;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

    private String createWord(int... letter) {
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < letter.length; i++) {
            builder.append((char) (letter[i] + 'a'));
        }

        return builder.toString();
    }

    public static void main(String[] args) {
        new WordSequence().run();
    }

}