Tagged Questions

For questions about dividing groups of objects based on their properties.

21 views

23 views

How to get increasing int number based on two values

I did ask this question on SO but it seems this will find more appropriate audience here. I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
17 views

Derive a probability distribution to transform scalars for weighted random sampling

Let's say I have a case with only two choices: $N_a$ = 20 $N_b$ = 10 I want to find a probability distribution that I can map these two values too, such that the probability of one variable being ...
36 views

Expected number of permutations required to sort a list of numbers

Given a list of N numbers if we are performing random permutations each time and checking whether the list is sorted, what will be the expected number of permutations required to sort that list?
14 views

2D Bin Packing with Ordering Along One Dimension

This is my second attempt at solving this particular problem (original is here: Topological sort into a limited number of bins, each with limited capacity). For clarity, I have reproduced the relevant ...
27 views

Topological sort into a limited number of bins, each with limited capacity

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together ...
19 views

How to sort a list of tuples?

I am neither a mathematician, nor a computer scientist, but I have the following problem, which I cannot solve myself. I have $k$ $i$-tuples $(x_1, x_2, …, x_i)$, where $x ∈ [0,1]$. I need to order ...
23 views

Sort a set of points to minimize the sum of the square distances between two consecutive points

Let $P$ be a finite set of points in $\mathbb{R}^3$. Let the number of points in $P$ be $n\in\mathbb{N}$. I want to sort the points in $P$ to minimize the sum of the distances between two consecutive ...
47 views

why can't sort 12 elements in 29 comparisons

The information theoretic lower bound for sorting 12 elements is using 29 comparisons, but actually we can't sort them in less than 30 comparisons. My problem is that why we can't reach the ...
7 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
24 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
56 views

Comparison between $n\log n$ and $n^2$ sorting algorithms

Suppose we have two sorting algorithms which takes $O(n\log n)$ and $O(n^2)$ time. What can we say about it? Is it always better to choose $n\log n$ if the size $n$ is not given? Or can we say on an ...
24 views

Looking for an equation that reflects the majority of a collection

I'm working on a computer program, part of which involves sifting through large collections of numbers (by large, I mean 16 million+ numbers). I expect these collections to almost entirely be composed ...
21 views

How to sort ten coin for twenty single weightings? [closed]

We can sorting 10 coin for 20 weighting, don't it? We can know which of the two coins is heavier for one weighting. Any two coin have different weight.
13 views

Finding the Reccurrence of a Periodic Sorting Network

Consider this Periodic Network of input size $n = 8$. I am trying to find an asymptotic approximation of the size (# of comparators) for such network. My attempt: Since there are $n$ inputs, there ...
13 views

For which $k$ I could sort permutation?

Suppose we have some permutation: $$p = a_{1}..a_{n}$$ We could inverse some subarray length of $k$. So my question is: for which $k$ I could sort my permutation using only my $k$-inverse? Obviously ...
59 views

Formulating an equation for a group sorting program.

I'm trying to formulate an equation/algorithm to solve this problem (for a program I'm writing): Rules: A person, p, that is to be sorted can exclude n amount of people from the list. The excluded ...
34 views

Vector sort operator

I was wondering whether there exists a definition of the sort operator for vector, i.e., the operator that given a vector of $\mathbb{R}^n$ yields a vector of $\mathbb{R}^n$ whose components are ...
49 views

Randomized Quick Sort and Partition Probability?

We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes. Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
47 views

Break a tie in a sum of a series of points

I'm an engineer and a programmer, NOT a mathematician. I hope that I am able to describe my problem well enough for you to understand, even though I'm incapable of asking it in "mathematician speak". ...
33 views

The complexity of bubble sort and insertion sort for a list with a given number of inversions

Let the length of a list be $n$, and the number of inversions be $d$. Why does insertion sort run in $O(n+d)$ time and why does bubble sort not? When I consider this problem I am thinking of the ...
15 views

How to sort list with Bayesian inference?

I have long list of Instagram accounts with the following data: number of followers of the account (N); number of users, who follows both this and mine accounts (n). I would like to get list of ...
21 views

Sorting Algorithm for weakly ordered list

I am aware of some sorting algorithms and there pros and cons but my question is specifically: What is a good sorting algorithm for a list that is generally but not strictly increasing, i.e. 1 5 4 8 5 ...
76 views

Is It Possible to Represent the Fractional Part of a Number as an Integer?

This question may not even have an answer in mathematics, so I apologize if it is too dumb. I am writing an algorithm to order a series of numbered items. These items have a unique numbering style ...
116 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
47 views

Sorting almost sorted array in $O(n)$ time

What is the best way to sort an array that has at least half of its elements in their final position? Is it possible to achieve $O(n)$ running time?
17 views

21 views

Type(s) of Hashing function that keeps the ordering information

I am asking this question from a perspective that we need to store a set of hashed data that can be queried later for in an ordered fashion. My situation is that some data has to be encrypted, I am ...
24 views

Sorting triangles by hypotenuse length

I have some points in $xy$ space and I need to sort distances between these points. If I calculate real distance, then I need to perform $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ and this is very time ...
142 views

Displaying a graph with minimum overlapping edges

Context I am developing UI for a skill web for a mobile game. Each skill may have requirements from other skills, or sometimes no requirement at all. The problem The description above is ...
45 views

Ideal amount of piles to sort a stack of 250 cards (magic the gathering)

I'm a hobbyist working on a mechanical sorting machine to sort magic the gathering cards. I'm by no means a mathematician though, and I was wondering if you all wouldn't mind helping me out with a ...
69 views

A lower bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal in the sense that is it a lower bound for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ ...
74 views

find which two points an arbitrary point is nearest to

I have a line segment of connected points (a path in 2D), and a point $P$ that is not calculated based on this segment, although I can guarantee that the point will be placed along the path. Based on ...
40 views

How to divide items into nearly equal sized groups

I teach a class with about $N=290$ students who will be taking an exam next week. The exam consists of two sections ($A$ and $B$) each with 6 essay questions. Students must answer one essay question ...
101 views

How many recursive calls are made when quicksort is size n [closed]

How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? I thought the answer is n times because isnt this the best case?