21221

среда, 22 июня 2016 г.

Permutation algorithm with JavaScript

http://www.pixelstech.net/article/1316620955-Permutation-algorithm-with-JavaScript

In secondary school, we have learned permutation. Basically, for n numbers, the number of permutations for these n numbers can be calculated to n! which is called 'n factorial'. But to display all the permutations on the screen, we need to use a recursive function. The problem is how to write this function. 

Next I write a program to display the permutations for n numbers with JavaScript. First, we need to understand that from these n numbers, we can first take any one number from it, and the (n-1) numbers remaining has the similar property as the n numbers, we need to find the permutations for the (n-1) numbers, and from these (n-1) numbers, we take any one of them and there are (n-2) numbers which we need to find the permutations of them. So the whole process will stop when there is only one number left, we will can display the permutations. It is a recursive process. The code can be shown below:

create all permutation of a string

http://www.thatjsdude.com/interview/js1.html#permutation

Question: How would you create all permutation of a string?
Answer: This could be a tough one based on you level of knowledge about algorithm.

function permutations(str){
var arr = str.split(''),
    len = arr.length, 
    perms = [],
    rest,
    picked,
    restPerms,
    next;

    if (len == 0)
        return [str];

    for (var i=0; i<len; i++)
    {
        rest = Object.create(arr);
        picked = rest.splice(i, 1);

        restPerms = permutations(rest.join(''));

       for (var j=0, jLen = restPerms.length; j< jLen; j++)
       {
           next = picked.concat(restPerms[j]);
           perms.push(next.join(''));
       }
    }
   return perms;
}
        
Explanation:
  • Idea: Idea is very simple. We will convert the string to an array. from the array we will pick one character and then permute rest of it. After getting the permutation of the rest of the characters, we will concatenate each of them with the character we have picked.
  • step-1 First copy original array to avoid changing it while picking elements
  • step-2 Use splice to removed element from the copied array. We copied the array because splice will remove the item from the array. We will need the picked item in the next iteration.
  • step-3 [1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
  • step-4 Use recursive method to get the permutation of the rest of the elements by passing array as string
  • step-5 Finally, concat like a+permute(bc) for each

умножение матрицы на число

Определение.
 Произведением матрицы A на число k называется матрица B = k · A того же размера, полученная из исходной умножением на заданное число всех ее элементов:
bi,j = k · ai,j

Свойства умножения матрицы на число

  • 1 · A = A
  • 0 · A = Θ, где Θ - нулевая матрица
  • k · (A + B) = k · A + k · B
  • (k + n) · A = k · A + n · A
  • (k · n) · A = k · (n · A)

отсюда...

сложение и вычитание матриц

Складывать и вычитать можно матрицы одного размера в результате получается матрица того же размера.
Определение.
 Сложение матриц (сумма матриц) A + B есть операция вычисления матрицы C, все элементы которой равны попарной сумме всех соответствующих элементов матриц A и B, то есть каждый элемент матрицы C равен:
сij = aij + bij
Определение.
 Вычитание матриц (разность матриц) A - B есть операция вычисления матрицы C, все элементы которой равны попарной разности всех соответствующих элементов матриц A и B, то есть каждый элемент матрицы C равен:
сij = aij - bij


Свойства сложения и вычитания матриц

  • Ассоциативность: (A + B) + C = A + (B + C)
  • A + Θ = Θ + A = A, где Θ - нулевая матрица
  • A - A = Θ
  • Коммутативность: A + B = B + A

отсюда...

пятница, 17 июня 2016 г.

переустановить Windows 10

сейчас у меня на ноутбуке Windows 10, бесплатно установленная с 8.1...
в настоящее время -- присутствуют некоторые проблемы, например, не работает Пуск...
я хочу снова переустановить Windows 10...
как мне это сделать?..
1) Создать загрузочный носитель той же редакции, что и Ваша 10-ка:
2) Выполнить чистую установку с созданного носителя:

четверг, 16 июня 2016 г.

вращение векторов (заметка)

эта заметка — личная...
лежит пока вот тут:
palaeo.spb.ru/algorithms/vector_rotation/

вращение векторов

http://palaeo.spb.ru/algorithms/vector_rotation_1993_24-26.pdf


умножение матрицы на вектор

результирующий вектор:

y = Ax
пример:


Тасование Фишера–Йетса

https://ru.wikipedia.org/wiki/Тасование_Фишера–Йетса

Тасование Фишера–Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайноготасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, и не требует дополнительного пространства.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
Современный вариант алгоритма тасования Фишера-Йетса, предназначенный для использования в компьютерах, был представлен Ричардом Дурштенфельдом (Richard Durstenfeld) в 1964-м году в журнале Communications of the ACM том 7, выпуск 7, под названием «Algorithm 235: Random permutation», и был популяризован Дональдом Кнутом во втором томе его книги Искусство программирования как «Алгоритм P». Ни Дуршенфельд, ни Кнут в первом издании книги не упомянули об алгоритме Фишера и Йетса, и, похоже, не были осведомлены о нём. Во втором издании книги Искусство программирования, однако, это упущение было исправлено
Алгоритм, описанный Дуршенфельдом, отличается от алгоритма Фишера и Йетса в небольших, но существенных деталях. Чтобы компьютерная реализация алгоритма не тратила бесполезно время на перебор оставшихся чисел на шаге 3, у Дуршенфельда на каждой итерации выбираемые числа переносились в конец списка путём перестановки с последним невыбранным числом. Эта модификация сокращала временную сложность алгоритма до O(n), по сравнению с O(n2) для исходного алгоритма. Это изменение приводит к следующему алгоритму.
Для тасования массива a из n элементов (индексы 0..n-1):
  для всех i от n − 1 до 1 выполнить
       j ← случайное число 0 ≤ j ≤ i
       обменять местами a[j] и a[i]

Math.random

http://javascript.ru/math.random

Синтаксис

var randomNumber = Math.random();

Описание, примеры

Заметим, что числа в яваскрипт хранятся в формате с плавающей точкой IEEE 754 с округлением в сторону ближайшего четного. Поэтому иногда, в очень редких случаях, возможна генерация обычно исключенной верхней границы.
Пример: Cлучайное число от 0(включительно) до 1
1function getRandom()
2{
3  return Math.random();
4}
Пример: Случайное число между min и max
1function getRandomArbitary(min, max)
2{
3  return Math.random() * (max - min) + min;
4}
Пример: Случайное целое между min и max
1// использование Math.round() даст неравномерное распределение!
2function getRandomInt(min, max)
3{
4  return Math.floor(Math.random() * (max - min + 1)) + min;
5}