Сделать все элементы массива уникальными
Есть массив с 10 элементами, содержащими числа от 0 до 20. Надо сделать так, чтобы не было одинаковых элементов, чтобы они заменились на любое другое число (от 0 до 20). Ума не приложу, как это сделать.
Готовый код не нужен, просто подкиньте алгоритм, как это всё организовать. |
Код:
WhoIs = {} |
а если сразу формировать массив с уникальными элементами ? чтоб его потом не проверять на повторы
|
рони, тогда массив станет меньше. А если добавить в него рандомное число, оно может совпасть с каким-нибудь оставшимся в массиве числом.
micscr, а причём тут хэш? |
Цитата:
|
Цитата:
|
-------------
Есть вариант — напустить на массив array_unique, потом, пока массив не примет прежний размер, добавлять в него рандомные числа, предварительно проверяя, не нахоятся ли они уже внутри него. Но порядок чисел должен сохраняться, поэтому это не подходит. |
Цитата:
|
функция формирования массива с уникальными данными с заданной длиной и диапазоном
<script language="JavaScript" type="text/javascript">
function random(min,max,l)
{var arr = [],m = [],n = 0;
if (max - min < l-1) return;
for (var i=0; i<=(max-min); i++)m[i] = i + min;
for (var i=0; i<l; i++) {n = Math.floor(Math.random()*(m.length)); arr[i]=m.splice(n,1)[0];};
return arr
}
document.write(JSON.stringify(random(0,20,10)))
</script>
|
вариант отлова на скорую руку
<script language="JavaScript" type="text/javascript">
function usefloor(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
var m = [],
s = [],
t = [];
var l = 10; //длина массива
var min = 0;
var max = 20;
//создание массива m с неуникальными элементами
for (var i = 0; i < l; i++) {
m[i] = usefloor(min, max)
}
var test="<br>" + m;
//создание массива t из оставшихся элементов на случай замены
for (var i = 0; i <= (max - min); i++) {
s[i] = 1;
}
for (var i = 0; i < l; i++) {
s[m[i]] = 0;
}
for (var i = 0; i < s.length; i++) {
if (s[i] == 1) t.push(i)
}
test+="<br>" + t;
//проверка m на уникальность и замена повторяющихся элементов
for (var i = 0; i < l; i++) {
for (var k = i + 1; k < l; k++) {
if (m[k] == m[i]) {
n = usefloor(0, (t.length - 1));
m[k] = "<font color='#FF0000'>" + t[n] + "</font>";
t.splice(n, 1);
}
}
}
document.write(test+"<br>" + m);
</script>
|
|
рони, спасибо за помощь. То, что нужно.
|
Здравствуйте. При использовании данной функции,взятой из этой темы(спасибо рони), очень часто выскакивает значение "undefined". Не могу понять, где я накосячил переделывая написанное рони в функцию.
function addArray(letterOfArray, arrayOfCorrelation) {
function usefloor(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
var m = [],
s = [],
t = [];
var l = 9; //длина массива
var min = 1;
var max = 9;
//создание массива m с неуникальными элементами
for (var i = 0; i < l; i++) {
m[i] = usefloor(min, max)
}
var test = m;
//создание массива t из оставшихся элементов на случай замены
for (var i = 0; i <= (max - min); i++) {
s[i] = 1;
}
for (var i = 0; i < l; i++) {
s[m[i]] = 0;
}
for (var i = 0; i < s.length; i++) {
if (s[i] == 1) t.push(i)
}
test = t;
//проверка m на уникальность и замена повторяющихся элементов
for (var i = 0; i < l; i++) {
for (var k = i + 1; k < l; k++) {
if (m[k] == m[i] || m[k]=="undefined") {
n = usefloor(1, (t.length - 1));
m[k] = t[n];
t.splice(n, 1);
}
}
}
for (var i = 0; i < l; i++) {
var count = i + 1;
document.getElementById(letterOfArray + count).value = m[i];
}
var arrayOfCorrelation =this.arrayOfCorrelation= m;
return arrayOfCorrelation;
}
var arrayA;
addArray("a", arrayA);
addArray("b", arrayA);
addArray("c", arrayA);
addArray("d", arrayA);
addArray("e", arrayA);
addArray("f", arrayA);
addArray("g", arrayA);
addArray("h", arrayA);
addArray("i", arrayA);
document.write(arrayA);
|
Stroy,
Вы лучше описали бы, что Вы хотите получить в итоге? Случайно перемешанный массив ?
function Peremeshivalka(lng){
var a = {},i,out=[],n=0;
for(i=0;i<lng;i++)a[i]=i;
while (n!=lng){
i = Math.floor(lng*Math.random());
if(typeof(a[i])!='undefined'){
out.push(a[i]);
delete a[i];
n++;
}
}
return out;
}
var arr = "abcdefghi".split(''); //Массив перемешивания;
var lng = arr.length;
var index = Peremeshivalka(lng);
var out = [];
for(var i=0;i<lng;i++)out.push(arr[index[i]]);
alert(out)
|
Deff,
Есть 2-х мерный массив 9Х9. Хочу построчно заполнить его случайными числами в диапазоне 1-9. Каждая ячейка имеет свой id. Буква(a-i)+цифра от1-9. С функцией взятой из этой темы вроде все получается. Но частенько во второй половине массива по горизонтали вместо числа, выдается значение undefied. |
Stroy,
так взяли бы код из 9 поста и запустили девять раз , а не проверочный из 10 или вам нужно чтоб кроме строк и столбцы были разными?судоку ? |
Цитата:
При каждом запуске получите массив случайный из 9 элементов
function Peremeshivalka(lng){
var a = {},i,out=[],n=0;
for(i=0;i<lng;i++)a[i]=i;
while (n!=lng){
i = Math.floor(lng*Math.random());
if(typeof(a[i])!='undefined'){
out.push(a[i]+1); //Добавил 1(чтобы не от 0)
delete a[i];
n++;
}
}
return out;
}
var out =[];
for(var i=0;i<9;i++){ out.push(Peremeshivalka(9).join(','));}
alert(out.join(',\n'))
//
========================== Хотя пост 9 делает тож самое не хуже // Замерил на 10000 элементах - мой быстрее :) (наверно splice(n,1)[0]; дольше, чем delete a[i]; |
Цитата:
|
Deff,
Спасибо. Попробую прикрутить Вашу функцию. Или ф-цию рони из поста 9. |
судоку sudoku
Stroy,
Судоку, простая генерация в лоб :) ... если вы видите число 300000 значит вам не повезло. :cray:
<!DOCTYPE HTML>
<html>
<head>
<title>sudoku</title>
<meta charset="utf-8">
</head>
<body>
<script>
Array.prototype.shuffle = function() {
for (var a = this.length - 1; 0 < a; a--) {
var b = Math.floor(Math.random() * (a + 1)),
c = this[b];
this[b] = this[a];
this[a] = c
}
return this
};
for (var arr = [], b = [], obj = {}, column = {}, d = 0, i = 0; 9 > i; i++)
b.push(i + 1), obj[i] = {}, column[i] = {};
for (var k = 0; 9 > k;) {
b = b.slice().shuffle();
var a = b.every(function(c, e, f) {
f = (e / 3 | 0) + 3 * (k / 3 | 0);
return !obj[f][c] && !column[e][c]
});
d++;
if (300000 <= d) break;
a && (arr.push(b), b.forEach(function(c, e, f) {
obj[(e / 3 | 0) + 3 * (k / 3 | 0)][c] = column[e][c] = !0
}), k++)
};
document.write(arr.join('<br>')+ '<br>'+d)
</script>
</body>
</html>
|
рони,
Ну по идее - 90% судоку мон получить по первому столбцу, сдвигая элементы первого столбца для генерации следующего на один элемент по кругу Т.е. первый - генерим рандомно с наличием всех цифр по высоте, второй получаем сдвигая элементы первого столбца по кругу)мон не на один элемент, а на два(произвольное число), но идентично на такое же число для всех последующих столбцов 1 4 3 2 2 1 4 3 3 2 1 4 4 3 2 1 =========== И да, проще наверно сдвигать по строкам(метода идентична) Т.е рандом первой строки и рандом цифры циклического сдвига для всех строк |
Deff,
не уверен что твой алгоритм правильный, где гарантия что квадрат три на три будет заполнен уникально... |
рони,
Я уже делал так, сам подумай по логике! (Там еще потом мон еще строки, или столбцы свапировать (обменивать с друг с другом) случайным образом, после заполнения таблички такой методой(типо раширения вариаций) Свиг соседних не может быть кратен числу элементов в строке или столбце( а так произвольный, наверно меньше строка(или столбец).length, не помню уже, и постоянен для всех строк. |
Deff,
нет кода, нет результата, нет дум :) |
Цитата:
|
рони,
Я сбацаю, делал на фортране ёщё(Просто табличку доделываю для рулетки) |
Deff,
подожду код. Цитата:
|
Cм. Спойлер:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta name="robots" content="noindex">
<title> Sudoku </title>
<script src='http://code.jquery.com/jquery-1.11.0.js'></script>
<style>
#out {
table-layout:fixed;
}
#out td{
width:34px;
height:34px;
text-align:center;
vaertical-align: middle;
}
#out,
#out tr,
#out td{
padding: 0px;
margin: 0px;
border:none 0;
border-collapse:collapse;
}
#out td{
border: rgba(0,0,0,.1) solid 1px;
}
</style>
</head>
<body>
<div id=wrap><table id=out><tbody></tbody></table></div>
<p></p>
<p></p>
<input type="number" min="2" max="20" value="4" id="in00"><input type="button" value="go" onclick="randomSudoku(+(in00.value))">
<script>
function indexRandom(lng){
var a = {},i,out=[],n=0;
for(i=0;i<lng;i++)a[i]=i;
while (n!=lng){
i = Math.floor(lng*Math.random());
if(typeof(a[i])!='undefined'){
out.push(a[i]);
delete a[i];
n++;
}
}
return out;
}
randomSudoku = function (lng) {
var ind = indexRandom(lng); //рандом первой строки;
var ranTR = indexRandom(lng); //рандом перекида порядка строк в таблице;
var ranCols = indexRandom(lng); //рандом перекида порядка стобцов в таблице;
var ar0 = [],arr = [],i,j;
ar0[0]=ind; //Рандом для первой строки
for(i=1;i<lng;i++){ //Формируем табличку
ar0[i]=ar0[i-1].slice(0);
ar0[i].unshift(ar0[i].pop());
}
for(i=0;i<lng;i++){ //рандом стобцов;
arr[i]=[];
for(j=0;j<lng;j++)arr[i][j]=ar0[i][ranCols[j]];
}
var out=[];$('#out tr').remove();
for(i=0;i<lng;i++){
out[i]=arr[ranTR[i]];//рандом строк;
var str ='<tr>';
for(j=0;j<lng;j++)str+='<td>'+out[i][j]+'</td>';
str+='</tr>';$('#out tbody').append(str)
}
}
</script>
</body>
</html>
========================== Гы, хотя это может еще не судоку - посмотрел Вики(я то неповторяемость по строкам и столбцам смотрел, а там ток с 9Х9 и чоб в 3Х3 не повторялось); Можа завтра докую... А может и Судоку... (Засыпаю ... нужон критик...) |
Deff,
судоку варианты заполнения по строкам - критично 6 строка - если нет вариантов - 5 строка неправильный вариант по квадратам - не пробовал пока по цифрам- сначала 9 единичек и т.д. - неправильные варианты могут возникать уже на третей цифре ... самый пробивной вариант строить дерево :write: |
рони,
Да, я изучил Википедь, вроде есть одна идейка... Но чот я седни недоспал... мож к вечеру... Ксать иногда выходят если десятка два перебрать ... но пока не интересно перебором... нун алгоритм попробовать... |
Вроде родил алгоритм, если не отвлекут седни выложу
|
Ну вчерне(осталось еще парочку рандомов сделать...
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta name="robots" content="noindex">
<title> Sudoku </title>
<script src='http://code.jquery.com/jquery-1.11.0.js'></script>
<style>
#out td{
width:34px;
height:34px;
text-align:center;
vaertical-align: middle;
}
#out,
#out tr,
#out td{
padding: 0px;
margin: 0px;
border:none 0;
border-collapse:collapse;
}
#out td{
border: rgba(0,0,0,.2) solid 1px;
color: rgba(0,0,204,.611)
}
#out td:nth-child(3n+1) {
border-left: rgba(0,0,0,.2) solid 3px;
}
#out tr:nth-child(3n) {
border-bottom: rgba(0,0,0,.2) solid 3px;
}
#out{
table-layout:fixed;
border-top: rgba(0,0,0,.2) solid 3px;
border-right: rgba(0,0,0,.2) solid 3px;
}
</style>
</head>
<body>
<div id=wrap><table id=out><tbody>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</tbody></table></div>
<p></p>
<p></p>
<input type="button" value="Запустить!" onclick="getSudoku ()">
<script>
function indexRandom(lng){
var a = {},i,out=[],n=0;
while (n!=lng){
i = Math.floor(lng*Math.random());
if(typeof(a[i])=='undefined'){
a[i]=i;
out.push(a[i]);
n++;
}
}
return out;
}
//Cдвиг группы из N строк на n-ячеек влево;
function shiftLinetoN(Nstart,N,n,arr){
var j,x;
for(j=Nstart;j<Nstart+N;j++){
for(x=0;x<n;x++)arr[j].unshift(arr[j].pop());
}
}
//Рандомная перестановка группы из трёх строк;
function swap3nLines (Nstart,arr){
var i,del,index = indexRandom(3);
del = arr.slice(Nstart,Nstart+3);
for(i=0;i<3;i++) arr[Nstart+index[i]]=del[i];
}
getSudoku = function () {
var i,j,ind, arr = []; //Таблица;
var line0 = arr[0] = [1,2,3,4,5,6,7,8,9];
//Рандом-Перестановка элементов первой строки;
var ind=indexRandom(9); arr[0].forEach(function (x,i){arr[0][i]=ind[i]+1;});
var line1 = arr[1] = arr[0].slice(0); shiftLinetoN(1,1,3,arr);
var line2 = arr[2] = arr[1].slice(0); shiftLinetoN(2,1,3,arr);
//Cоздаём остальные cтроки таблицы;
for(j=3;j<9;j++){
arr[j]=arr[j%3].slice(0);
if(j%3==2) shiftLinetoN(j-2,3,parseInt(j/3),arr);
}
//Рандом-Перестановка строк в триадах строк;
for(j=0;j<6;j++){
if(j%3==2) swap3nLines(j-2,arr);
}
//Записываем в таблу
$('#out td').each(function (j){
$(this).html(arr[parseInt(j/9)][j%9]);
});
}
//alert(JSON.stringify(del))
</script>
</body>
</html>
|
Deff,
:dance: |
рони,
Ну еще осталось покрутить матрицу и перестановки триад меж собою рони, Ночью Вчера осенило, (из перво-сделанной таблицы), двигать в первой триаде не на одну ячейку а на высоту минитаблы, а в остальных метод тот жа, чо и в первоначальном скрипте |
Deff,
:yes: |
Забавно, из 10 000 табличек подряд, не повторилось ни одной... (создались за 40 сек...
Гы, из 100 000 тож ни одного повтора (388 сек) =========================== Статистика на миллионе табличек: дважды повторились идентичные: 9359, (0.9% от всех) Трижды: 110, Четырежды: 3; =========== Время создания: 4230сек; ________________________________________________ Выяснил что за 800 000 антикореляционные возможности текущих перестановок существенно снижаются, вероятнсть совпадений возрастает... Мон прикинуть число комбинаций за счет перестановок наверно в районе 10^7 - 10^8 Нун добавлять Варианты перестановок. Википедь пишет, что число Вариантов табличек в районе 10^21 (Т.е у меня чичас 21/3 (= 7) - не хватает как раз двух вариантов свапа триад и кручения матрицы |
.forEach Замедлил в 4 раза с 4.5с на 1000 до 20с (ужос)
Выкинул нафиг(удобен но не для длинных тестов) |
Deff,
:) |
Deff, если есть желание проверь на повторяемость :)
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
<style type="text/css">
div{
border: 3px groove #8B4513;
float: left;
}
</style>
</head>
<body>
<script>
Array.prototype.shuffle = function() {
for (var a = this.length - 1; 0 < a; a--) {
var b = Math.floor(Math.random() * (a + 1)),
c = this[b];
this[b] = this[a];
this[a] = c
}
return this
};
function fn() {
for (var f = [], b = [], g = {}, h = {}, n = 0, a = 0; 9 > a; a++) b.push(a + 1), g[a] = {}, h[a] = {};
for (var c = 0; 9 > c;) {
for (var a = b.slice(), d = [], k = 0; 9 > d.length;) {
var l = d.length,
q = (l / 3 | 0) + 3 * (c / 3 | 0),
e = (3 > l ? a.slice(-6) : a).filter(function(a) {
return !h[l][a] && !g[q][a] && -1 === d.indexOf(a)
});
if (e.length) {
var m = Math.floor(Math.random() * e.length),
e = e[m];
d.push(e);
m = a.indexOf(e);
a.splice(m, 1)
} else a = b.slice(), d = [];
k++;
if (50 <= k) {
k = 0;
break
}
}
a = d.concat(a.shuffle());
b = !c || a.every(function(a, p, b) {
b = (p / 3 | 0) + 3 * (c / 3 | 0);
return !g[b][a] &&
!h[p][a]
});
n++;
if (40 <= n) break;
b ? (f.push(a), a.forEach(function(a, b, d) {
g[(b / 3 | 0) + 3 * (c / 3 | 0)][a] = h[b][a] = !0
}), c++) : (c--, 0 > c && (c = 0), a = f[c] || [], f.length = c, a.forEach(function(a, b, d) {
g[(b / 3 | 0) + 3 * (c / 3 | 0)][a] = h[b][a] = !1
}));
b = a
}
return 9 == f.length ? f : fn()
};
var d = performance.now();
for (var i=0; i<10000 ; i++) {fn()};
alert('10000 => '+((performance.now()-d)/100|0)/10 + 's') //время генерации 10000
for (var i=0; i<500 ; i++) {document.write('<div>'+fn().join('<br>')+'</div>') }//500 вариантов для визуальной проверки
</script>
</body>
</html>
|
Ну да, у тьву шустро - 10000 за 3.5 сек(В Мозилле)) (Но у я свой тестил со старой оперы, своё там существенно медленней, и второе - у мну добавлено еще рандомы и кручение таблы. Ксать неплохо бы выводить цифру текущего кол-ва, а то в Опере думал зависло
|
| Часовой пояс GMT +3, время: 21:07. |